Institutional Repository of Vilnius University
Sekoskaitos fragmentų sulyginimo su referentiniu genomu algoritmų tyrimas /
Abstract
dc:descriptionAnalysis of Next Generation Sequencing Real Alignment Algorithms Next-generation sequencing methods generate a tremendous amount of short nucleotide sequence reads. Each sequence read needs to be mapped to a unique location in a reference genome – a task which calls for an efficient computational solution. In this work I propose a novel algorithm for short read alignment – Qligner. The algorithm splits each read into a number of fixed-length potentially overlapping seeds (n-grams). Indexed genomic occurrences of the n-grams are then used to vote on the potential location. Several coordinates that match the greatest number of seeds are selected for further evaluation. Longest common subsequence is used as a similarity metric to choose the candidate with the minimum number of mismatches with the original read. I compared the proposed algorithm with popular short read aligners in terms of speed, sensitivity, and specificity. BWA mem was more sensitive than any other solution, but it was also the slowest. In 60-100 bp read length range Qligner demonstrated sensitivity and specificity similar to that of BWA mem and Bowtie 2 while surpassing both in terms of speed. The algorithm is sensitive to parameters and can be tweaked to prioritise either speed or accuracy.
Degree
thesis:*- Grantor dc:publisher
- Institutional Repository of Vilnius University
- Year dc:date
- 2016
Author and committee
dc:creator, dc:contributor.*- Author dc:creator
-
- Smoliakov, Aleksandr Jan,
- Contributors dc:contributor
-
- Gordevičius, Juozas
Rights
dc:rights- Statement dc:rights
-
- info:eu-repo/semantics/openAccess
- Language dc:language
- lit
Identifiers
dc:identifier.*- Repository record dc:identifier
- https://repository.vu.lt/VU:ELABAETD20088129&prefLang=en_US