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.
Tang
Chuan Yi
CY
Department of Computer Science, National Tsing Hua University, Hsinchu 300, Taiwan, ROC. cytang@cs.nthu.edu.tw
Lu
Chin Lung
CL
Chang
Margaret Dah-Tsyr
MD
Tsai
Yin-Te
YT
Sun
Yuh-Ju
YJ
Chao
Kun-Mao
KM
Chang
Jia-Ming
JM
Chiou
Yu-Han
YH
Wu
Chia-Mao
CM
Chang
Hao-Teng
HT
Chou
Wei-I
WI
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