We found a match
Your institution may have access to this item. Find your institution then sign in to continue.
- Title
Efficient construction of an assembly string graph using the FM-index.
- Authors
Simpson, Jared T; Durbin, Richard
- Abstract
Sequence assembly is a difficult problem whose importance has grown again recently as the cost of sequencing has dramatically dropped. Most new sequence assembly software has started by building a de Bruijn graph, avoiding the overlap-based methods used previously because of the computational cost and complexity of these with very large numbers of short reads. Here, we show how to use suffix array-based methods that have formed the basis of recent very fast sequence mapping algorithms to find overlaps and generate assembly string graphs asymptotically faster than previously described algorithms.
- Publication
Bioinformatics (Oxford, England), 2010, Vol 26, Issue 12, pi367
- ISSN
1367-4811
- Publication type
Journal Article
- DOI
10.1093/bioinformatics/btq217