File Download
 
Links for fulltext
(May Require Subscription)
 
Supplementary

Conference Paper: High throughput short read alignment via bi-directional BWT
  • 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 FieldValue
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
 
<?xml encoding="utf-8" version="1.0"?>
<item><contributor.author>Lam, TW</contributor.author>
<contributor.author>Li, R</contributor.author>
<contributor.author>Tam, A</contributor.author>
<contributor.author>Wong, S</contributor.author>
<contributor.author>Wu, E</contributor.author>
<contributor.author>Yiu, SM</contributor.author>
<date.accessioned>2010-12-23T08:39:26Z</date.accessioned>
<date.available>2010-12-23T08:39:26Z</date.available>
<date.issued>2009</date.issued>
<identifier.citation>The IEEE International Conference on Bioinformatics and Biomedicine (BIBM 2009), Washington, DC., 1-4 November 2009. In Proceedings of BIBM, 2009, p. 31-36</identifier.citation>
<identifier.isbn>978-0-7695-3885-3</identifier.isbn>
<identifier.uri>http://hdl.handle.net/10722/129577</identifier.uri>
<description.abstract>The 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. &#169; 2009 IEEE.</description.abstract>
<language>eng</language>
<publisher>IEEE.</publisher>
<relation.ispartof>Proceedings of the IEEE International Conference on Bioinformatics and Biomedicine, BIBM 2009</relation.ispartof>
<rights>IEEE International Conference on Bioinformatics and Biomedicine. Copyright &#169; IEEE.</rights>
<rights>Creative Commons: Attribution 3.0 Hong Kong License</rights>
<rights>&#169;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.</rights>
<subject>BWT</subject>
<subject>Indexing data structure</subject>
<subject>Short read alignment</subject>
<title>High throughput short read alignment via bi-directional BWT</title>
<type>Conference_Paper</type>
<identifier.openurl>http://library.hku.hk:4550/resserv?sid=HKU:IR&amp;issn=978-0-7695-3885-3&amp;volume=&amp;spage=31&amp;epage=36&amp;date=2009&amp;atitle=High+throughput+short+read+alignment+via+bi-directional+BWT</identifier.openurl>
<description.nature>published_or_final_version</description.nature>
<identifier.doi>10.1109/BIBM.2009.42</identifier.doi>
<identifier.scopus>eid_2-s2.0-74549131724</identifier.scopus>
<identifier.hkuros>177020</identifier.hkuros>
<relation.references>http://www.scopus.com/mlt/select.url?eid=2-s2.0-74549131724&amp;selection=ref&amp;src=s&amp;origin=recordpage</relation.references>
<identifier.spage>31</identifier.spage>
<identifier.epage>36</identifier.epage>
<identifier.isi>WOS:000275900200006</identifier.isi>
<description.other>The IEEE International Conference on Bioinformatics and Biomedicine (BIBM 2009), Washington, DC., 1-4 November 2009. In Proceedings of BIBM, 2009, p. 31-36</description.other>
<identifier.citeulike>6497555</identifier.citeulike>
<bitstream.url>http://hub.hku.hk/bitstream/10722/129577/1/Content.pdf</bitstream.url>
</item>
Author Affiliations
  1. The University of Hong Kong
  2. Beijing Genomics Institute, Shenzhen