Sequence assembly
From Wikipedia, the free encyclopedia
In bioinformatics, sequence assembly refers to aligning and merging many fragments of a much longer DNA sequence in order to reconstruct the original sequence. Typically the short fragments result from shotgun sequencing genomic DNA, or gene transcript (ESTs).
First-Generation sequence assemblers began to appear in the late 1980s and early 1990s, to piece together vast quantities of fragments generated by automated sequencing instruments. These First-Generation assemblers employed several strategies to handle repetitive sequences (repeats) and sequencing errors, which can confound assembly. However, they could not handle genomes much larger than a bacterium (several million DNA bases), and they were eventually replaced as the field moved up to bigger genomes. The following are First-Generation assemblers, widely used during the 1990s in academia, government, and industry:
- Phrap, by Phil Green, The University of Washington
- TIGR Assembler. by Granger Sutton, The Institute for Genomic Research
- CAP3, by Xiaoqiu Huang, Michigan Technological University
Contents |
[edit] Assemblers for large genome
Faced with the challenge of assembling the much larger genomes of the fruit fly Drosophila melanogaster in 2000 and the human genome just a year later, scientists developed assemblers like Celera Assembler (first developed by a private company) and Arachne able to handle genomes of 100-300 million base pairs. Subsequent to these efforts, several other groups, mostly at the major genome sequencing centers, built large-scale assemblers, and an open source effort known as AMOS was launched to bring together all the innovations in genome assembly technology under the open source framework.
EST assembly differs from genome assembly in several ways. For instance, genomes often have large amounts of repetitive sequences, mainly in the intra-genic parts. Since ESTs represent gene transcripts, they will not contain these repeats. On the other hand, genes sometimes overlap in the genome (sense-antisense transcription), and should ideally still be assembled separately. EST assembly is also complicated by features like (cis-) alternative splicing, trans-splicing, single-nucleotide polymorphism, recoding, and post-transcriptional modification. These differences make the new generation assemblers less applicable to EST assembly.
[edit] Greedy algorithm
Given a set of sequence fragments the object is to find the Shortest common supersequence.
- calculate pairwise alignments of all fragments
- choose two fragments with the largest overlap
- merge chosen fragments
- repeat step 2. and 3. until only one fragment is left
The result is a suboptimal solution to the problem.
