High Throughput Short Read Alignment via Bi-directional BWT

被引：78

作者：

Lam, T. W. ^{[1
]}

Li, Ruiqiang ^{[2
]}

Tam, Alan ^{[1
]}

Wong, Simon ^{[1
]}

Wu, Edward ^{[1
]}

Yiu, S. M. ^{[1
]}

机构：

[1] Univ Hong Kong, Dept Comp Sci, Hong Kong, Hong Kong, Peoples R China

[2] Beijing Genom Inst Shenzhen, Shenzhen 518083, Peoples R China

来源：

2009 IEEE INTERNATIONAL CONFERENCE ON BIOINFORMATICS AND BIOMEDICINE | 2009年

关键词：

short read alignment; BWT; indexing data structure; HUMAN GENOME; DNA;

D O I：

10.1109/BIBM.2009.42

中图分类号：

Q5 [生物化学];

学科分类号：

071010 ; 081704 ;

摘要：

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 BWT is an interesting data structure on its own and could be applied to other pattern matching problems.

引用

页码：31 / +

页数：2

共 18 条

[11] Ultrafast and memory-efficient alignment of short DNA sequences to the human genome [J].

Langmead, Ben ;

Trapnell, Cole ;

Pop, Mihai ;

Salzberg, Steven L. .

GENOME BIOLOGY, 2009, 10 (03)

[12] Mapping short DNA sequencing reads and calling variants using mapping quality scores [J].

Li, Heng ;

Ruan, Jue ;

Durbin, Richard .

GENOME RESEARCH, 2008, 18 (11) :1851-1858

[13] SOAP: short oligonucleotide alignment program [J].

Li, Ruiqiang ;

Li, Yingrui ;

Kristiansen, Karsten ;

Wang, Jun .

BIOINFORMATICS, 2008, 24 (05) :713-714

[14] ZOOM! Zillions of oligos mapped [J].

Lin, Hao ;

Zhang, Zefeng ;

Zhang, Michael Q. ;

Ma, Bin ;

Li, Ming .

BIOINFORMATICS, 2008, 24 (21) :2431-2437

[15] Space-efficient whole genome comparisons with Burrows-Wheeler transforms [J].

Lippert, RA .

JOURNAL OF COMPUTATIONAL BIOLOGY, 2005, 12 (04) :407-415

[16] Rank and select revisited and extended [J].

Makinen, Veli ;

Navarro, Gonzalo .

THEORETICAL COMPUTER SCIENCE, 2007, 387 (03) :332-347

[17] Genome-wide profiles of STAT1 DNA association using chromatin immunoprecipitation and massively parallel sequencing [J].

Robertson, Gordon ;

Hirst, Martin ;

Bainbridge, Matthew ;

Bilenky, Misha ;

Zhao, Yongjun ;

Zeng, Thomas ;

Euskirchen, Ghia ;

Bernier, Bridget ;

Varhol, Richard ;

Delaney, Allen ;

Thiessen, Nina ;

Griffith, Obi L. ;

He, Ann ;

Marra, Marco ;

Snyder, Michael ;

Jones, Steven .

NATURE METHODS, 2007, 4 (08) :651-657

[18] The diploid genome sequence of an Asian individual [J].

Wang, Jun ;

Wang, Wei ;

Li, Ruiqiang ;

Li, Yingrui ;

Tian, Geng ;

Goodman, Laurie ;

Fan, Wei ;

Zhang, Junqing ;

Li, Jun ;

Zhang, Juanbin ;

Guo, Yiran ;

Feng, Binxiao ;

Li, Heng ;

Lu, Yao ;

Fang, Xiaodong ;

Liang, Huiqing ;

Du, Zhenglin ;

Li, Dong ;

Zhao, Yiqing ;

Hu, Yujie ;

Yang, Zhenzhen ;

Zheng, Hancheng ;

Hellmann, Ines ;

Inouye, Michael ;

Pool, John ;

Yi, Xin ;

Zhao, Jing ;

Duan, Jinjie ;

Zhou, Yan ;

Qin, Junjie ;

Ma, Lijia ;

Li, Guoqing ;

Yang, Zhentao ;

Zhang, Guojie ;

Yang, Bin ;

Yu, Chang ;

Liang, Fang ;

Li, Wenjie ;

Li, Shaochuan ;

Li, Dawei ;

Ni, Peixiang ;

Ruan, Jue ;

Li, Qibin ;

Zhu, Hongmei ;

Liu, Dongyuan ;

Lu, Zhike ;

Li, Ning ;

Guo, Guangwu ;

Zhang, Jianguo ;

Ye, Jia .

NATURE, 2008, 456 (7218) :60-U1

← 1 2 →