SEAL: A divide and conquer approach for sequence alignment.

摘要

Sequence similarity search and sequence alignment methods are fundamental steps in comparative genomics and have a wide spectrum of application in the field of medicine, agriculture and environment. The Dynamic Programming sequence alignment method produces optimal alignments but is impractical for a similarity search due to its huge running time. Heuristic methods like BLAST run much faster but may not provide optimal alignments. A novel sequence alignment method called SEAL is introduced here. SEAL uses a combination of divide-and-conquer and the maximum contiguous sub-array solution. This method is improved by the use of the borders in every contiguous segment. The alignment scores obtained by SEAL are consistently higher than those obtained by heuristic methods.