Author : Suchindra Suchindra and Preetam Nagaraj

Biological sequence alignment is common today and are used in a variety of fields ranging from Bioinformatics, Computational Biology, Genome analysis, Cancer research, Stem Research and many more fields. Most of these fields use the sequence alignment to find the ‘similar’ regions or similarities between organisms. Since, this step is computational heavy, today, there are specialized hardware to help speed up and techniques and strategies to help speed up or improve the sensitivity (quality) of the alignment in general. The early successful algorithms in sequence alignment were focused on quality, and it produced an optimal algorithm called SmithWaterman algorithm, which we will discuss in detail later using a technique called ‘Dynamic Programming’. The time complexity of this algorithms was O (mn). Later, to speedup, heuristic algorithms were developed. Heuristic algorithms gave up a little bit on the quality for speed, by calculating the near-optimal alignment rather than optimal algorithm. In this paper, we will analyze various computational approaches for local sequence alignments.

Keywords: Bioinformatics, Computational, Dynamic, Heuristic.