Mapping short reads to a genome without using hash look-up table algorithm and Burrows Wheeler Transformation

Chun Yuan Lin; Ming Yuan Huang; Chia Han Chu; Petrus Tang; Chuan Yi Tang

doi:10.1109/BIBMW.2009.5332100

Mapping short reads to a genome without using hash look-up table algorithm and Burrows Wheeler Transformation

Chun Yuan Lin, Ming Yuan Huang, Chia Han Chu, Petrus Tang, Chuan Yi Tang

Department of Parositology

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › peer-review

2 Scopus citations

Abstract

Many new sequencing techniques have been proposed in the last few years. A number of tools have been developed for mapping short reads to the genome. However, these tools used the hash look-up table algorithm for reads or for the genome. With more and more reads sequenced and the length of reads increases; these tools will require huge memory usage and may be not practical for biologists and applications. Recently, new tools were designed to overcome this problem by using Burrows Wheeler Transformation. In this paper, we propose a program, FRESCO, without using hash look-up table algorithm and Burrows Wheeler Transformation. By well-designed techniques in FRESCO, the memory usage can be controlled by users. A case study of micro-RNAs (miRNAs) was applied into FRESCO and the results showed that FRESCO can only used 268MB memory and mapped reads to all of known miRNAs and 98.6% novel miRNAs candidates.

Original language	English
Title of host publication	Proceedings - 2009 IEEE International Conference on Bioinformatics and Biomedicine Workshops, BIBMW 2009
Pages	232-237
Number of pages	6
DOIs	https://doi.org/10.1109/BIBMW.2009.5332100
State	Published - 2009
Event	2009 IEEE International Conference on Bioinformatics and Biomedicine Workshops, BIBMW 2009 - Washington, DC, United States Duration: 01 11 2009 → 04 11 2009

Publication series

Name	Proceedings - 2009 IEEE International Conference on Bioinformatics and Biomedicine Workshops, BIBMW 2009

Conference

Conference	2009 IEEE International Conference on Bioinformatics and Biomedicine Workshops, BIBMW 2009
Country/Territory	United States
City	Washington, DC
Period	01/11/09 → 04/11/09

Keywords

Approximate string matching
Burrows Wheeler Transformation
Hash look-up table algorithm
New sequencing techniques

Access to Document

10.1109/BIBMW.2009.5332100

Cite this

Lin, C. Y., Huang, M. Y., Chu, C. H., Tang, P., & Tang, C. Y. (2009). Mapping short reads to a genome without using hash look-up table algorithm and Burrows Wheeler Transformation. In Proceedings - 2009 IEEE International Conference on Bioinformatics and Biomedicine Workshops, BIBMW 2009 (pp. 232-237). Article 5332100 (Proceedings - 2009 IEEE International Conference on Bioinformatics and Biomedicine Workshops, BIBMW 2009). https://doi.org/10.1109/BIBMW.2009.5332100

Lin, Chun Yuan ; Huang, Ming Yuan ; Chu, Chia Han et al. / Mapping short reads to a genome without using hash look-up table algorithm and Burrows Wheeler Transformation. Proceedings - 2009 IEEE International Conference on Bioinformatics and Biomedicine Workshops, BIBMW 2009. 2009. pp. 232-237 (Proceedings - 2009 IEEE International Conference on Bioinformatics and Biomedicine Workshops, BIBMW 2009).

@inproceedings{c16f274f87494ecbb82aebd4e8be3b4f,

title = "Mapping short reads to a genome without using hash look-up table algorithm and Burrows Wheeler Transformation",

abstract = "Many new sequencing techniques have been proposed in the last few years. A number of tools have been developed for mapping short reads to the genome. However, these tools used the hash look-up table algorithm for reads or for the genome. With more and more reads sequenced and the length of reads increases; these tools will require huge memory usage and may be not practical for biologists and applications. Recently, new tools were designed to overcome this problem by using Burrows Wheeler Transformation. In this paper, we propose a program, FRESCO, without using hash look-up table algorithm and Burrows Wheeler Transformation. By well-designed techniques in FRESCO, the memory usage can be controlled by users. A case study of micro-RNAs (miRNAs) was applied into FRESCO and the results showed that FRESCO can only used 268MB memory and mapped reads to all of known miRNAs and 98.6% novel miRNAs candidates.",

keywords = "Approximate string matching, Burrows Wheeler Transformation, Hash look-up table algorithm, New sequencing techniques",

author = "Lin, {Chun Yuan} and Huang, {Ming Yuan} and Chu, {Chia Han} and Petrus Tang and Tang, {Chuan Yi}",

year = "2009",

doi = "10.1109/BIBMW.2009.5332100",

language = "英语",

isbn = "9781424451210",

series = "Proceedings - 2009 IEEE International Conference on Bioinformatics and Biomedicine Workshops, BIBMW 2009",

pages = "232--237",

booktitle = "Proceedings - 2009 IEEE International Conference on Bioinformatics and Biomedicine Workshops, BIBMW 2009",

note = "2009 IEEE International Conference on Bioinformatics and Biomedicine Workshops, BIBMW 2009 ; Conference date: 01-11-2009 Through 04-11-2009",

}

Lin, CY, Huang, MY, Chu, CH, Tang, P & Tang, CY 2009, Mapping short reads to a genome without using hash look-up table algorithm and Burrows Wheeler Transformation. in Proceedings - 2009 IEEE International Conference on Bioinformatics and Biomedicine Workshops, BIBMW 2009., 5332100, Proceedings - 2009 IEEE International Conference on Bioinformatics and Biomedicine Workshops, BIBMW 2009, pp. 232-237, 2009 IEEE International Conference on Bioinformatics and Biomedicine Workshops, BIBMW 2009, Washington, DC, United States, 01/11/09. https://doi.org/10.1109/BIBMW.2009.5332100

Mapping short reads to a genome without using hash look-up table algorithm and Burrows Wheeler Transformation. / Lin, Chun Yuan; Huang, Ming Yuan; Chu, Chia Han et al.
Proceedings - 2009 IEEE International Conference on Bioinformatics and Biomedicine Workshops, BIBMW 2009. 2009. p. 232-237 5332100 (Proceedings - 2009 IEEE International Conference on Bioinformatics and Biomedicine Workshops, BIBMW 2009).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › peer-review

TY - GEN

T1 - Mapping short reads to a genome without using hash look-up table algorithm and Burrows Wheeler Transformation

AU - Lin, Chun Yuan

AU - Huang, Ming Yuan

AU - Chu, Chia Han

AU - Tang, Petrus

AU - Tang, Chuan Yi

PY - 2009

Y1 - 2009

N2 - Many new sequencing techniques have been proposed in the last few years. A number of tools have been developed for mapping short reads to the genome. However, these tools used the hash look-up table algorithm for reads or for the genome. With more and more reads sequenced and the length of reads increases; these tools will require huge memory usage and may be not practical for biologists and applications. Recently, new tools were designed to overcome this problem by using Burrows Wheeler Transformation. In this paper, we propose a program, FRESCO, without using hash look-up table algorithm and Burrows Wheeler Transformation. By well-designed techniques in FRESCO, the memory usage can be controlled by users. A case study of micro-RNAs (miRNAs) was applied into FRESCO and the results showed that FRESCO can only used 268MB memory and mapped reads to all of known miRNAs and 98.6% novel miRNAs candidates.

AB - Many new sequencing techniques have been proposed in the last few years. A number of tools have been developed for mapping short reads to the genome. However, these tools used the hash look-up table algorithm for reads or for the genome. With more and more reads sequenced and the length of reads increases; these tools will require huge memory usage and may be not practical for biologists and applications. Recently, new tools were designed to overcome this problem by using Burrows Wheeler Transformation. In this paper, we propose a program, FRESCO, without using hash look-up table algorithm and Burrows Wheeler Transformation. By well-designed techniques in FRESCO, the memory usage can be controlled by users. A case study of micro-RNAs (miRNAs) was applied into FRESCO and the results showed that FRESCO can only used 268MB memory and mapped reads to all of known miRNAs and 98.6% novel miRNAs candidates.

KW - Approximate string matching

KW - Burrows Wheeler Transformation

KW - Hash look-up table algorithm

KW - New sequencing techniques

UR - http://www.scopus.com/inward/record.url?scp=72849107767&partnerID=8YFLogxK

U2 - 10.1109/BIBMW.2009.5332100

DO - 10.1109/BIBMW.2009.5332100

M3 - 会议稿件

AN - SCOPUS:72849107767

SN - 9781424451210

T3 - Proceedings - 2009 IEEE International Conference on Bioinformatics and Biomedicine Workshops, BIBMW 2009

SP - 232

EP - 237

BT - Proceedings - 2009 IEEE International Conference on Bioinformatics and Biomedicine Workshops, BIBMW 2009

T2 - 2009 IEEE International Conference on Bioinformatics and Biomedicine Workshops, BIBMW 2009

Y2 - 1 November 2009 through 4 November 2009

ER -

Lin CY, Huang MY, Chu CH, Tang P, Tang CY. Mapping short reads to a genome without using hash look-up table algorithm and Burrows Wheeler Transformation. In Proceedings - 2009 IEEE International Conference on Bioinformatics and Biomedicine Workshops, BIBMW 2009. 2009. p. 232-237. 5332100. (Proceedings - 2009 IEEE International Conference on Bioinformatics and Biomedicine Workshops, BIBMW 2009). doi: 10.1109/BIBMW.2009.5332100

Mapping short reads to a genome without using hash look-up table algorithm and Burrows Wheeler Transformation

Abstract

Publication series

Conference

Keywords

Access to Document

Other files and links

Fingerprint

Cite this