206 94

HIA: A genome mapper using hybrid index-based sequence alignment

Title
HIA: A genome mapper using hybrid index-based sequence alignment
Author
박기정
Keywords
Hybrid index; NGS; Mapper; Sequence alignment; Hash table index; Suffix array index
Issue Date
2015-12
Publisher
Springer
Citation
Algorithms for Molecular Biology, v. 10, NO 1, Article number 30, Page. 1-9
Abstract
Background: A number of alignment tools have been developed to align sequencing reads to the human reference genome. The scale of information from next-generation sequencing (NGS) experiments, however, is increasing rapidly. Recent studies based on NGS technology have routinely produced exome or whole-genome sequences from several hundreds or thousands of samples. To accommodate the increasing need of analyzing very large NGS data sets, it is necessary to develop faster, more sensitive and accurate mapping tools. Results: HIA uses two indices, a hash table index and a suffix array index. The hash table performs direct lookup of a q-gram, and the suffix array performs very fast lookup of variable-length strings by exploiting binary search. We observed that combining hash table and suffix array (hybrid index) is much faster than the suffix array method for finding a substring in the reference sequence. Here, we defined the matching region (MR) is a longest common substring between a reference and a read. And, we also defined the candidate alignment regions (CARs) as a list of MRs that is close to each other. The hybrid index is used to find candidate alignment regions (CARs) between a reference and a read. We found that aligning only the unmatched regions in the CAR is much faster than aligning the whole CAR. In benchmark analysis, HIA outperformed in mapping speed compared with the other aligners, without significant loss of mapping accuracy. Conclusions: Our experiments show that the hybrid of hash table and suffix array is useful in terms of speed for mapping NGS sequencing reads to the human reference genome sequence. In conclusion, our tool is appropriate for aligning massive data sets generated by NGS sequencing.
URI
http://www.almob.org/content/10/1/30http://hdl.handle.net/20.500.11754/29468
ISSN
1748-7188
DOI
10.1186/s13015-015-0062-4
Appears in Collections:
RESEARCH INSTITUTE[S](부설연구소) > ETC
Files in This Item:
HIA a genome mapper using hybrid index-based sequence alignment.pdfDownload
Export
RIS (EndNote)
XLS (Excel)
XML


qrcode

Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.

BROWSE