Paper Info
Title
High Throughput Short Read Alignment via Bi-directional BWT
Abstract
The advancement of sequencing technologies has made it feasible for researchers to consider many high-throughput 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 BWTis an interesting data structure on its own and couldbe applied to other pattern matching problems.
Year
DOI
Venue
2009
10.1109/BIBM.2009.42
BIBM
Keywords
Field
DocType
possible alignment,fastest software,bi-directional bwt,human genome,interesting data structure,alignment software,unique best alignment,high throughput short read,reference genome,new indexing data structure,faster software,high throughput,data structures,genomics,bwt,bioinformatics,data structure,indexation,pattern matching
Data structure,Data mining,Computer science,Search engine indexing,Genomics,Software,Bioinformatics,Throughput,Pattern matching,Reference genome
Conference
Volume
Issue
ISSN
null
null
2156-1125
ISBN
Citations 
PageRank 
978-0-7695-3885-3
44
2.03
References 
Authors
7
6
Name
Order
Citations
PageRank
Tak-Wah Lam11860164.96
Ruiqiang Li276591.23
Alan Tam3602.71
Simon Wong413811.68
Edward Wu52208.81
S. M. Yiu6442.03