Multiple Anchor Staged Local Sequence Alignment Algorithm - MASAA.

Technology advancements have helped biologists gather massive amount of biological data including genomic sequences of various species today. Sequence alignment techniques play a central role in investigating the adaptive significance of organism traits and revealing evolutionary relations among organisms by comparing these biological data. This thesis presents an algorithm to perform pairwise local sequence alignment. Recent pairwise local sequence alignment algorithms are either slow and sensitive or fast and less sensitive. Our algorithm is faster and at the same time sensitive. The algorithm employs suffix tree data structure to accurately identify long common subsequences in the two given sequences quickly. Regions of high similarity are again identified between segments of long subsequences already found. Several measures are taken into consideration to design the algorithm, such that the output is biologically meaningful. Data sets are carefully chosen and the output is compared with a well known algorithm, BLASTZ. Experiments conducted demonstrate that our algorithm performs better than BLASTZ in computation time, while either preserving or exceeding the accuracy of alignments at times.