Locating All Common Subsequences in Two DNA Sequences

Biological sequence comparison is one of the\udmost important and basic problems in computational\udbiology. Due to its high demands for computational\udpower and memory, it is a very challenging task. The\udwell-known algorithm proposed by Smith-Waterman\udobtains the best local alignments at the expense of very\udhigh computing power and huge memory requirements.\udThis paper introduces a new efficient algorithm to locate\udthe longest common subsequences (LCS) in two different\udDNA sequences. It is based on the convolution between\udthe two DNA sequences: The major sequence is\udrepresented in the linked-list X while the minor one is\udrepresented in circular linked-list Y. An array of linked\udlists is established where each linked list is corresponding\udto an element of the linked-list X and a new node is\udadded to it for each match between the two sequences. If\udtwo or more matches in different locations in string Y\udshare the same location in string X, the corresponding\udnodes will construct a unique linked-list. Accordingly, by\udthe end of processing, we obtain a group of linked-lists\udcontaining nodes that reflect all possible matches between\udthe two sequences X and Y. The proposed algorithm has\udbeen implemented and tested using C# language. The\udbenchmark test shows very good speedups and indicated\udthat impressive improvements has been achieved