New Local Sequence Alignment Algorithm with Adaptive Seeds and Maximum Match Subsequence (ASMMS)

Abstract

Sequence alignment is an important step in many fields today, from genome research to Pharma. It is famously used to determine how closely two sequences are related and at times to see how little they differ, example finding one’s relatives. In computational biology, there are algorithms developed over time to not only align two sequences quickly but also to get biological data. The very first algorithms developed were based off a technique called Dynamic Programming, which were slow but produced optimal alignment. To improve speed, more algorithms today are based off heuristic approach, sacrificing sensitivity. In this paper, we are going to improve on a heuristic algorithm which is accepted to be published in the Journal of Biosciences and Engineering (BIOEJ). This new algorithm appropriately called ASMMS, stands for Adaptive Seeds and Maximal Match Subsequence local alignment algorithm. The algorithm is based on suffix tree data structure, but to improve sensitivity, we employ adaptive seeds, and perfect match seeds in between the already identified maximal matches. We tested this algorithm on a randomly generated sequences, and small dataset of genes where the sequence length ranged up to 500 thousand, our algorithm performed better than the rest.