Conference Paper: High throughput short read alignment via bi-directional BWT

File Download Links for fulltext
(May Require Subscription)
Supplementary
  • Basic View
  • Metadata View
  • XML View
TitleHigh throughput short read alignment via bi-directional BWT
AuthorsLam, TW1
Li, R2
Tam, A1
Wong, S1
Wu, E1
Yiu, SM1
KeywordsBWT
Indexing data structure
Short read alignment
Issue Date2009
PublisherIEEE.
CitationThe IEEE International Conference on Bioinformatics and Biomedicine (BIBM 2009), Washington, DC., 1-4 November 2009. In Proceedings of BIBM, 2009, p. 31-36 [How to Cite?]
DOI: http://dx.doi.org/10.1109/BIBM.2009.42
AbstractThe advancement of sequencing technologies has made it feasible for researchers to consider many highthroughput biological applications. A core step of these applications is to align an enormous amount of short reads to a reference genome. For example, to resequence a human genome, billions of reads of 35 bp are produced in 1-2 weeks, putting a lot of pressure of faster software for alignment. Based on existing indexing and pattern matching technologies, several short read alignment software have been developed recently. Yet this is still strong need to further improve the speed. In this paper, we show a new indexing data structure called bi-directional BWT, which allows us to build the fastest software for aligning short reads. When compared with existing software (Bowtie is the best), our software is at least 3 times faster for finding unique best alignments, and 25 times faster for finding all possible alignments. We believe that bi-directional BWT is an interesting data structure on its own and could be applied to other pattern matching problems. Availability: http://www.bio5.cs.hku.hk:8080/P2BWT, where two human genomes are indexed for alignment. © 2009 IEEE.
ISBN978-0-7695-3885-3
DOIhttp://dx.doi.org/10.1109/BIBM.2009.42
ISI Accession Number IDWOS:000275900200006
ReferencesReferences in Scopus
DC Field
Value
dc.contributor.authorLam, TW
dc.contributor.authorLi, R
dc.contributor.authorTam, A
dc.contributor.authorWong, S
dc.contributor.authorWu, E
dc.contributor.authorYiu, SM
dc.date.accessioned2010-12-23T08:39:26Z
dc.date.available2010-12-23T08:39:26Z
dc.date.issued2009
dc.description.abstractThe advancement of sequencing technologies has made it feasible for researchers to consider many highthroughput biological applications. A core step of these applications is to align an enormous amount of short reads to a reference genome. For example, to resequence a human genome, billions of reads of 35 bp are produced in 1-2 weeks, putting a lot of pressure of faster software for alignment. Based on existing indexing and pattern matching technologies, several short read alignment software have been developed recently. Yet this is still strong need to further improve the speed. In this paper, we show a new indexing data structure called bi-directional BWT, which allows us to build the fastest software for aligning short reads. When compared with existing software (Bowtie is the best), our software is at least 3 times faster for finding unique best alignments, and 25 times faster for finding all possible alignments. We believe that bi-directional BWT is an interesting data structure on its own and could be applied to other pattern matching problems. Availability: http://www.bio5.cs.hku.hk:8080/P2BWT, where two human genomes are indexed for alignment. © 2009 IEEE.
dc.description.naturepublished_or_final_version
dc.description.otherThe IEEE International Conference on Bioinformatics and Biomedicine (BIBM 2009), Washington, DC., 1-4 November 2009. In Proceedings of BIBM, 2009, p. 31-36
dc.identifier.citationThe IEEE International Conference on Bioinformatics and Biomedicine (BIBM 2009), Washington, DC., 1-4 November 2009. In Proceedings of BIBM, 2009, p. 31-36 [How to Cite?]
DOI: http://dx.doi.org/10.1109/BIBM.2009.42
dc.identifier.citeulike6497555
dc.identifier.doihttp://dx.doi.org/10.1109/BIBM.2009.42
dc.identifier.epage36
dc.identifier.hkuros177020
dc.identifier.isbn978-0-7695-3885-3
dc.identifier.isiWOS:000275900200006
dc.identifier.openurl
dc.identifier.scopuseid_2-s2.0-74549131724
dc.identifier.spage31
dc.identifier.urihttp://hdl.handle.net/10722/129577
dc.languageeng
dc.publisherIEEE.
dc.relation.ispartofProceedings of the IEEE International Conference on Bioinformatics and Biomedicine, BIBM 2009
dc.relation.referencesReferences in Scopus
dc.rightsIEEE International Conference on Bioinformatics and Biomedicine. Copyright © IEEE.
dc.rightsCreative Commons: Attribution 3.0 Hong Kong License
dc.rights©2009 IEEE. Personal use of this material is permitted. However, permission to reprint/republish this material for advertising or promotional purposes or for creating new collective works for resale or redistribution to servers or lists, or to reuse any copyrighted component of this work in other works must be obtained from the IEEE.
dc.subjectBWT
dc.subjectIndexing data structure
dc.subjectShort read alignment
dc.titleHigh throughput short read alignment via bi-directional BWT
dc.typeConference_Paper
Author Affiliations
  1. The University of Hong Kong
  2. Beijing Genomics Institute, Shenzhen