Please use this identifier to cite or link to this item: http://scholarbank.nus.edu.sg/handle/10635/42143
Title: An experimental study of compressed indexing and local alignments of DNA
Authors: Lam, T.-W.
Sung, W.-K. 
Tam, S.-L.
Wong, C.-K.
Yiu, S.-M.
Issue Date: 2007
Source: 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.

Page view(s)

63
checked on Dec 9, 2017

Google ScholarTM

Check


Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.