An Efficient Algorithm for Mapping of Reads to a Genome Graph Using an Index Based on Hash Tables and Dynamic Programming |
| |
| Authors: | S. N. Petrov,L. A. Uroshlev,A. S. Kasyanov,V. Yu. Makeev |
| |
| Affiliation: | 1.Vavilov Institute of General Genetics,Russian Academy of Sciences,Moscow,Russia;2.Moscow Institute of Physics and Technology (State University), Institutskiy per. 9,Moscow oblast,Russia;3.Engelhardt Institute of Molecular Biology,Russian Academy of Sciences,Moscow,Russia;4.Research Institute for Genetics and Selection of Industrial Microorganisms,Kurchatov Institute Scientific Center,Moscow,Russia |
| |
| Abstract: | The problem of storage of the sequences of a number of closely related genomes and analysis of genome variations is considered. A genome graph with the structure of an acyclic directed graph is used to store matching sections of sequences and known variants. An algorithm for rapid mapping of reads to the genome graph is developed to align the individual nucleotide sequence fragments to the genome graph. The algorithm combines rapid searching using hash tables with the algorithm of dynamic programming and solves the problem of exponential growth in the number of paths on the graph. The implementation of the genome graph and the algorithm of the alignment of reads is developed. A comparison with the best-known programs with similar functionality is made. |
| |
| Keywords: | |
| 本文献已被 SpringerLink 等数据库收录！ |
|
