Abstract
Generally speaking, biologists have the knowledge of their datasets concerning the structures / functionalities / consensuses. The concept of constrained sequence alignment is proposed to incorporate the biologist's knowledge into sequence alignment such that the user-specified residues / nucleotides are aligned together in the computed alignment. Tang et al. were first to investigate constrained multiple sequence alignment problem. Their algorithm for two sequences alignment with constraints runs in time and need space. Later, this result was improved independently by two groups of researchers to time and space using the same approach of dynamic programming. Then, Chin Lung Lu designed a memory-efficient algorithm to improve the two sequence alignment with constraints by adopting the divide-and-conquer approach, this memory-efficient algorithm for solving CPSA problem can run in time and need only space, where is the sum of the length of constraints and usually in the practical applications. In this paper, we designed a parallel algorithm for the constrained multiple sequence alignment based on the memory-efficient algorithm designed by Chin Lung Lu and the progressive strategy. Then using this algorithm, we developed a parallel version tool for the constrained multiple sequence alignment.