Title :
Multiple sequence alignment using minimum spanning tree
Author :
Zhu, Mei-Jie ; Hu, Gui-wu ; Zheng, Qi-Lun ; Peng, Hong
Author_Institution :
Coll. of Comput. Sci. & Eng., South China Univ. of Technol., Guangzhou, China
Abstract :
Multiple sequence alignment (MSA) is one of the most important tools in modern biology. The MSA problem is NP-hard; therefore, heuristic approaches are needed to align a large set of data within a reasonable time. In this paper, a new MSA algorithm is proposed. We use a minimum spanning tree (MST) algorithm to construct a guide tree in which the sequences are aligned. The time complexity of our MSA approach is O(n 3L 2) (where n is the number of sequences and L is the maximum length of all sequences). The validity of our algorithm has been confirmed by the experimental results.
Keywords :
biology computing; computational complexity; molecular biophysics; tree searching; trees (mathematics); NP-hard problem; heuristic approach; minimum spanning tree; molecular biology; multiple sequence alignment; star alignment algorithm; time complexity; Agricultural engineering; Biology computing; Clustering algorithms; Computational biology; Computer science; Educational institutions; Mathematics; Phylogeny; Polymers; Sequences; Multiple sequence alignment; minimum spanning tree; molecular biology; star alignment algorithm;
Conference_Titel :
Machine Learning and Cybernetics, 2005. Proceedings of 2005 International Conference on
Conference_Location :
Guangzhou, China
Print_ISBN :
0-7803-9091-1
DOI :
10.1109/ICMLC.2005.1527521
