Please use this identifier to cite or link to this item:
|Title:||An experimental study of compressed indexing and local alignments of DNA||Authors:||Lam, T.-W.
|Issue Date:||2007||Citation:||Lam, T.-W.,Sung, W.-K.,Tam, S.-L.,Wong, C.-K.,Yiu, S.-M. (2007). An experimental study of compressed indexing and local alignments of DNA. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics) 4616 LNCS : 241-254. ScholarBank@NUS Repository.||Abstract:||Recent experimental studies on compressed indexes (BWT, CSA, FM-index) have confirmed their practicality for indexing long DNA sequences such as the human genome (about 3 billion characters) in the main memory [5,13,16]. However, these indexes are designed for exact pattern matching, which is too stringent for most biological applications. The demand is often on finding local alignments (pairs of similar sub-strings with gaps allowed). In this paper, we show how to build a software called BWT-SW that exploits a BWT index of a text T to speed up the dynamic programming for finding all local alignments with any pattern P. Experiments reveal that BWT-SW is very efficient (e.g., aligning a pattern of length 3,000 with the human genome takes less than a minute). We have also analyzed BWT-SW mathematically, using a simpler model (with gaps disallowed) and random strings. We find that the expected running time is O(|T| 0,628|P|). As far as we know, BWT-SW is the first practical tool that can find all local alignments. © Springer-Verlag Berlin Heidelberg 2007.||Source Title:||Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)||URI:||http://scholarbank.nus.edu.sg/handle/10635/42143||ISBN:||9783540735557||ISSN:||03029743|
|Appears in Collections:||Staff Publications|
Show full item record
Files in This Item:
There are no files associated with this item.
checked on May 31, 2019
Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.