Please use this identifier to cite or link to this item:
https://scholarbank.nus.edu.sg/handle/10635/42143
DC Field | Value | |
---|---|---|
dc.title | An experimental study of compressed indexing and local alignments of DNA | |
dc.contributor.author | Lam, T.-W. | |
dc.contributor.author | Sung, W.-K. | |
dc.contributor.author | Tam, S.-L. | |
dc.contributor.author | Wong, C.-K. | |
dc.contributor.author | Yiu, S.-M. | |
dc.date.accessioned | 2013-07-04T08:44:26Z | |
dc.date.available | 2013-07-04T08:44:26Z | |
dc.date.issued | 2007 | |
dc.identifier.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. | |
dc.identifier.isbn | 9783540735557 | |
dc.identifier.issn | 03029743 | |
dc.identifier.uri | http://scholarbank.nus.edu.sg/handle/10635/42143 | |
dc.description.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. | |
dc.source | Scopus | |
dc.type | Conference Paper | |
dc.contributor.department | COMPUTER SCIENCE | |
dc.description.sourcetitle | Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics) | |
dc.description.volume | 4616 LNCS | |
dc.description.page | 241-254 | |
dc.identifier.isiut | NOT_IN_WOS | |
Appears in Collections: | Staff Publications |
Show simple item record
Files in This Item:
There are no files associated with this item.
Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.