Constrained multiple sequence alignment tool development and its application to RNase family alignment.
In this paper, we design a heuristic algorithm of computing a constrained multiple sequence alignment (CMSA for short) for guaranteeing that the generated alignment satisfies the user-specified constraints that some particular residues should be aligned together. If the number of residues needed to be aligned together is a constant alpha, then the time-complexity of our CMSA algorithm for aligning K sequences is O(alphaKn(4)), where n is the maximum of the lengths of sequences. In addition, we have built up such a CMSA software system and made several experiments on the RNase sequences, which mainly function in catalyzing the degradation of RNA molecules. The resulting alignments illustrate the practicability of our method.
Department of Computer Science, National Tsing Hua University, Hsinchu 300, Taiwan, ROC. cytang@cs.nthu.edu.tw
Chuan Yi
CY
Tang
Chin Lung
CL
Lu
Margaret Dah-Tsyr
MD
Chang
Yin-Te
YT
Tsai
Yuh-Ju
YJ
Sun
Kun-Mao
KM
Chao
Jia-Ming
JM
Chang
Yu-Han
YH
Chiou
Chia-Mao
CM
Wu
Hao-Teng
HT
Chang
Wei-I
WI
Chou
D000465:Algorithms; D000595:Amino Acid Sequence; D008969:Molecular Sequence Data; D012260:Ribonucleases / Q000032:analysis / Q000737:chemistry* / Q000145:classification*; D016415:Sequence Alignment / Q000379:methods*; D020539:Sequence Analysis, Protein / Q000379:methods*; D017386:Sequence Homology, Amino Acid; D012984:Software
D012260:Ribonucleases