運用生物資訊演算法建構演化樹

Bioinformatics Computing: Evolutionary Tree Construction

余姍(Shan Yu)

指導教授 ： 陳宗天

共同指導教授 ： 何善輝(Shan-Hui Ho)

國立臺北大學/商學院/資訊管理研究所/碩士(2009年)

摘要

無資料

關鍵字

生物資訊 ； 演化樹建構 ； 平行運算 ； 基因序列比對

並列摘要

The applications of evolutionary trees have been widely applied in many related biological and biomedical problems. These problems can be multiple sequence alignment, protein structure and its associated function predictions, and drug design. Many of them such as phylogenies construction and multiple sequence alignment are very computationally demanding. Constructing any evolutionary tree is very time consuming and has been recognized as a NP problem. In this thesis, we proposed a DNA algorithm for any evolutionary tree construction based upon bioinformatics computing. This DNA algorithm is fully utilizing parallelism to conquer algorithm complexity bottleneck constructs any evolutionary tree much more efficient. The experimental results shows that the complexity for all of different evolutionary tree constructions in the same time is in O(n3) polynomial bound.

並列關鍵字

Bioinformatics ； Evolutionary Tree ； Parallelism ； Multiple Sequence Alignment

參考文獻

17. Guo, J., Chen, L., Qin, L., & Wang, C. (2006). A Self-adaptive Ant Colony Algorithm for Phylogenetic Tree Construction. Paper presented at the 2006 International Conference on Hybrid Information Technology (ICHIT'06).

21. Hung, J.-Y. (2008). Bioinformatics Logic Computing: Using the HP Lattice Model for Protein Structure Optimal Prediction. Ming-Chung University, Tau-Yuan county.

1. Adleman, L. M. (1994). Molecular computation of solutions to combinatorial problems. Science, 266(5187), 1021-1024.

2. Boneh, D., Dunworth, C., Lipton, R. J., & Sgall, J. (1996). On the computational power of DNA. Discrete Applied Mathematics, 71(1), 79-94.

3. Cancino, W., & Delbem, A. C. B. (2007). Multi-Criterion Phylogenetic Inference using Evolutionary Algorithms. Paper presented at the IEEE Symposium on Computational Intelligence and Bioinformatics and Computational Biology, 2007. CIBCB'07.