title: HIA: a genome mapper using hybrid index-based sequence alignment.
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.
authors.affiliation: Division of Bio-Medical Informatics, Center for Genome Science, Korea National Institute of Health, Osong, Korea.
authors.forename: Jongpill
authors.initials: J
authors.lastname: Choi
authors.affiliation: Biomedical Research Institute, College of Medicine, Hanyang University, Seoul, Korea.
authors.forename: Kiejung
authors.initials: K
authors.lastname: Park
authors.affiliation: Division of Bio-Medical Informatics, Center for Genome Science, Korea National Institute of Health, Osong, Korea.
authors.forename: Seong Beom
authors.initials: SB
authors.lastname: Cho
authors.affiliation: Division of Bio-Medical Informatics, Center for Genome Science, Korea National Institute of Health, Osong, Korea.
authors.forename: Myungguen
authors.initials: M
authors.lastname: Chung
keywords: Hash table index; Hybrid index; Mapper; NGS; Sequence alignment; Suffix array index