Conference Paper: An experimental study of compressed indexing and local alignments of DNA
| Title | An experimental study of compressed indexing and local alignments of DNA |
|---|---|
| Authors | Lam, TW1 Sung, WK2 Tam, SL1 Wong, CK1 Yiu, SM1 |
| Issue Date | 2007 |
| Publisher | Springer Verlag. The Journal's web site is located at http://springerlink.com/content/105633/ |
| Citation | Lecture Notes In Computer Science (Including Subseries Lecture Notes In Artificial Intelligence And Lecture Notes In Bioinformatics), 2007, v. 4616 LNCS, p. 241-254 [How to Cite?] |
| 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. |
| ISSN | 0302-9743 2011 SCImago Journal Rankings: 0.034 |
| References | References in Scopus |
| dc.contributor.author | Lam, TW |
|---|---|
| dc.contributor.author | Sung, WK |
| dc.contributor.author | Tam, SL |
| dc.contributor.author | Wong, CK |
| dc.contributor.author | Yiu, SM |
| dc.date.accessioned | 2010-09-25T14:52:13Z |
| dc.date.available | 2010-09-25T14:52:13Z |
| dc.date.issued | 2007 |
| 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.description.nature | Link_to_subscribed_fulltext |
| dc.identifier.citation | Lecture Notes In Computer Science (Including Subseries Lecture Notes In Artificial Intelligence And Lecture Notes In Bioinformatics), 2007, v. 4616 LNCS, p. 241-254 [How to Cite?] |
| dc.identifier.epage | 254 |
| dc.identifier.hkuros | 146741 |
| dc.identifier.issn | 0302-9743 2011 SCImago Journal Rankings: 0.034 |
| dc.identifier.scopus | eid_2-s2.0-38149082263 |
| dc.identifier.spage | 241 |
| dc.identifier.uri | http://hdl.handle.net/10722/93144 |
| dc.identifier.volume | 4616 LNCS |
| dc.language | eng |
| dc.publisher | Springer Verlag. The Journal's web site is located at http://springerlink.com/content/105633/ |
| dc.publisher.place | Germany |
| dc.relation.ispartof | Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics) |
| dc.relation.references | References in Scopus |
| dc.title | An experimental study of compressed indexing and local alignments of DNA |
| dc.type | Conference_Paper |
Author Affiliations
- The University of Hong Kong
- National University of Singapore