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

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

參考文獻

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.

5. Cazenave, T. (2007). Overestimation for Multiple Sequence Alignment. Paper presented at the Proceedings of the 2007 IEEE Symposium on Computational Intelligence in Bioinformatics and Computational Biology (CIBCB 2007).

6. Chang, W.-L., Guo, M., & Ho, M. S.-H. (2005). Fast Parallel Molecular algorithms for DNA-Based Computation: Factoring Integers. IEEE Transactions on Nanobioscience, 4(2), 149-163.