ДНК тізбегін құрастыру және биоақпараттық алгоритмдер

In bioinformatics, sequence assembly refers to aligning and merging fragments from a longer DNA sequence in order to reconstruct the original sequence. This is needed as DNA sequencing technology might not be able to 'read' whole genomes in one go, but rather reads small pieces of between 20 and 30,000 bases, depending on the technology used. Typically, the short fragments (reads) result from shotgun sequencing genomic DNA, or gene transcript (ESTs). The problem of sequence assembly can be compared to taking many copies of a book, passing each of them through a shredder with a different cutter, and piecing the text of the book back together just by looking at the shredded pieces. Besides the obvious difficulty of this task, there are some extra practical issues: the original may have many repeated paragraphs, and some shreds may be modified during shredding to have typos. Excerpts from another book may also be added in, and some shreds may be completely unrecognizable.

Expressed sequence tag or EST assembly was an early strategy, dating from the mid 1990s to the mid 2000s, to assemble individual genes rather than whole genomes. The problem differs from genome assembly in several ways. The input sequences for EST assembly are fragments of the transcribed mRNA of a cell and represent only a subset of the whole genome. A number of algorithmical problems differ between genome and EST assembly. For instance, genomes often have large amounts of repetitive sequences, concentrated in the intergenic regions. Transcribed genes contain many fewer repeats, making assembly somewhat easier. On the other hand, some genes are expressed (transcribed) in very high numbers (e. g., housekeeping genes), which means that unlike whole genome shotgun sequencing, the reads are not uniformly sampled across the genome. EST assembly is made much more complicated by features like (cis ) alternative splicing, trans splicing, single nucleotide polymorphism, and post transcriptional modification. Beginning in 2008 when RNA Seq was invented, EST sequencing was replaced by this far more efficient technology, described under de novo transcriptome assembly.

In terms of complexity and time requirements, de novo assemblies are orders of magnitude slower and more memory intensive than mapping assemblies. This is mostly due to the fact that the assembly algorithm needs to compare every read with every other read (an operation that has a naive time complexity of O(n2)). Current de novo genome assemblers may use different types of graph based algorithms, such as the:

Overlap/Layout/Consensus (OLC) approach, which was typical of the Sanger data assemblers and relies on an overlap graph. de Bruijn Graph (DBG) approach, which is most widely applied to the short reads from the Solexa and SOLiD platforms. It relies on K mer graphs, which performs well with vast quantities of short reads. Greedy graph based approach, which may also use one of the OLC or DBG approaches. With greedy graph based algorithms, the contigs grow by greedy extension, always taking on the read that is found by following the highest scoring overlap. Referring to the comparison drawn to shredded books in the introduction: while for mapping assemblies one would have a very similar book as a template (perhaps with the names of the main characters and a few locations changed), de novo assemblies present a more daunting challenge in that one would not know beforehand whether this would become a science book, a novel, a catalogue, or even several books. Also, every shred would be compared with every other shred. Handling repeats in de novo assembly requires the construction of a graph representing neighboring repeats. Such information can be derived from reading a long fragment covering the repeats in full or only its two ends. On the other hand, in a mapping assembly, parts with multiple or no matches are usually left for another assembling technique to look into.

Most sequence assemblers have some algorithms built in for quality control, such as Phred. However, such measures do not assess assembly completeness in terms of gene content. Some tools evaluate the quality of an assembly after the fact. For instance, BUSCO (Benchmarking Universal Single Copy Orthologs) is a measure of gene completeness in a genome, gene set, or transcriptome, using the fact that many genes are present only as single copy genes in most genomes. The initial BUSCO sets represented 3023 genes for vertebrates, 2675 for arthropods, 843 for metazoans, 1438 for fungi and 429 for eukaryotes. This table shows an example for human and fruit fly genomes:
+BUSCO notation assessment results (C,D,F, M in %)SpeciesgenesC:D:F:M:n:Homo sapiens20,364 991.70.00.03,023Drosophila melanogaster13,918993.70.20.02,675