Local alignment on highly unbalanced dna sequence lengths by reducing search space

Abstract

DNA local sequence alignments provide biological insights that can help scientists identify genetic diseases, map newly obtained sequences to known genomes, or identify common genomic patterns on same species. Even when optimal sequence alignment algorithms have been well understood since more than 3 decades ago, the technological advancements of Next Generation Sequencing and the genomic data explosion they produced made them impractical today. Moreover, there is an increasingly necessity of fast comparison of very small sequences (less than 5,000 base pairs) against full genomes (greater than 100M base pairs). This thesis focuses on the local alignment problem for sequences with extreme length disparity and presents an Improved Search for a Local Alignment (ISLA) algorithm which provides an iteration based algorithm that achieves near optimal results by focusing local alignment only on specic areas of interest. ISLA also provides a probabilistic model to understand the chances of achieving a higher score.