A new hash function and its use in read mapping on genome

Document Type : Original Article

Authors

1 Department of Mathematics and computer science, Amirkabir University of Technology, Tehran, Iran

2 National Institute of Genetic Engineering and Biotechnology, Tehran, Iran

Abstract

Mapping reads onto genomes is an indispensable step in sequencing data analysis. A widely used method to speed up mapping is to index a genome by a hash table, in which genomic positions of $k$-mers are stored in the table. The hash table size increases exponentially with the $k$-mer length and thus the traditional hash function is not appropriate for a $k$-mer as long as a read. We present a hashing mechanism by two functions named $score1$ and $score2$ which can hash sequences with the length of reads. The size of hash table is directly proportional to the genome size, which is absolutely lower than that of hash table built by the conventional hash function. We evaluate our hashing system by developing a read mapper and running the mapper on $E. coli$ genome with some simulated data sets. The results show that the high percentage of simulated reads can be mapped to correct locations on the genome.

Keywords

Main Subjects

References

[1] A. Ahmadi, A. Behm, N. Honnalli, C. Li, L. Weng, X. Xie, Hobbes: optimized gram-based methods for efficient read alignment, Nucleic Acids Research, 40(6) (2011) e41-e41.
[2] N. Homer, B. Merriman, S. F. Nelson, BFAST: An alignment tool for lLarge scale genome resequencing. PLoS ONE, 14(11) (2009) 1-12.
[3] B. Langmead, S. L. Salzberg, Fast gapped-read alignment with Bowtie 2. Nature Methods, 9(4) (2012) 357-359.
[4] B. Langmead, C. Trapnell, M. Pop, S. L. Salzberg, Ultrafast and memory-efficient alignment of short DNA sequences to the human genome, Genome Biology, 10(3) (2009) R25.
[5] W-P. Lee, M. P. Stromberg, A. Ward, C. Stewart, E. P. Garrison, G. T. Marth. Mosaik: A hash-based algorithm for accurate next-generation sequencing short-read mapping, PLOS ONE, 9(3) (2014) 1-11.
[6] H. Li and R. Durbin. Fast and accurate short read alignment with burrows-wheeler transform, Bioinformatics, 25(14) (2009) 1754-1760.
[7] S. M. Rumble, P. Lacroute, A. V. Dalca, M. Fiume, A. Sidow, M. Brudno, Shrimp: Accurate mapping of short color-space reads, PLOS Computational Biology, 5(5) (2009) 1-11.
[8] A. D. Smith, W-Y. Chung, E. Hodges, J. Kendall, G. Hannon, J. Hicks, Z. Xuan, M. Q. Zhang, Updates to the RMAP short-read mapping software, Bioinformatics, 25(21):2841–2842, 2009.
[9] T. F. Smith, M. S. Waterman, Identification of common molecular subsequences, Journal of Molecular Biology, 147(1) (1981) 195-197.
[10] H. Zhang, Y. Chan, K. Fan, B. Schmidt, W. Liu, Fast and efficient short read mapping based on a succinct hash index, BMC Bioinformatics, 19(1):92, 2018.
AUT Journal of Mathematics and Computing
Volume 1, Issue 2
September 2020
Pages 165-170

Files

Share

How to cite

Statistics