Design of a New Deterministic Algorithm for Finding Common DNA Subsequence

Computational methods have become especially important since the advent of genome projects, whose objective is to decode the entire DNA sequence. Sequence motifs are short, recurring patterns in DNA that are presumed to have a biological function. These motifs are often responsible for similarity or dissimilarity in biological features and their DNA patterns. In this paper, we start with a database containing the set of DNA patterns. Our aim is to search motifs that occur in the same order where as other characters or gaps might occur between the motifs. We generalize it as a common sub-sequence problem from the computational aspect. The exponential nature of the problem is ischolar_mained in its definition in the sense that the solution set itself is expected to be exponential in size. In this work, a new deterministic subsequence matching algorithm for a set of DNA strings has been proposed from the computational perspective. The proposed deterministic algorithm yields the exhaustive set of common sub-sequences that many of its commercial counterparts cannot guarantee.