Multiple Anchor Staged Alignment Algorithm – Sensitive (MASAA – S)

Sequence alignment is common nowadays as it is used in computational biology or Bioinformatics to determine how closely two sequences are similar. There are many computational algorithms developed over the course of time to not only align two sequences. The first algorithms developed were based on a technique called Dynamic Programming which rendered them slow but produce optimal alignment. Today, however heuristic approach algorithms are popular as they are faster and yet produce near optimal alignment. In this paper, we are going to improve on a heuristic algorithm called MASAA (Multiple Anchor Staged Local Sequence Alignment Algorithm) - which we published previously. This new algorithm appropriately called MASAA - S stands for MASAA Sensitive. The algorithm is based on suffix tree data structure to identify anchors first, but to improve sensitivity, we employ adaptive seeds, and shorter perfect match seeds in between the already identified anchors. When the Anchors are separated by a greater distance than a threshold 'd', we exclude such anchors. We tested this algorithm on a randomly generated sequences, and Rosetta dataset where the sequence length ranged up to 500 thousand.