系統生物資訊運算:DNA序列重組最佳化

Systems Bioinformatics Computing: DNA Sequence Assembly Optimization

范修銘(Shiu-Ming Fan)

指導教授 ： 陳宗天

共同指導教授 ： 何善輝

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

摘要

DNA序列重組是一套將基因組序列組合、壓縮和有次序性，以應用序列的同源性與對應資訊來創造染色體一致序列。而基因組越大，重組運作則越困難。因此，DNA序列重組問題已被認定為NP-hard。在本論文中，我們建立一個系統生物資訊的模型，依據模型，提出並發展DNA最佳化演算法，不僅應用來修改霰彈槍法，而且特別設計DNA組合方法來求解有名的DNA序列重組問題。該新發展之演算法稱為DNA序列重組最佳化，先切割特定DNA序列成小片段群，然後重新組合這些小片段成為一個新序列，這新組合之序列可以適用在未來生物資訊發展基因工程的需求。本研究DNA演算法是利用平行去解決運算複雜度的瓶頸使解決DNA序列重組問題更有效率，解決DNA序列重組問題之實驗結果為多項式時間O(n^6)。

關鍵字

DNA序列重組 ； NP-hard問題 ； 系統生物資訊運算 ； 最佳化 ； 霰彈槍法 ； 平行

並列摘要

DNA sequence assembly is a set of genomic sequences that can be assembled,
condensed, and oriented by applying the sequence homology along with mapping information to create a consensus sequence of a chromosome. While larger any genome grows in size, while more difficult it is reassembled in optimization operations. Hence, the DNA sequence assembly problem has been recognized as NP-hard. In this thesis, we first construct a system bioinformatics model. Based upon this model, a DNA optimization algorithm is proposed and developed by not only applying and modifying the shotgun method but also utilizing a especially designed DNA assembly method to solve worldly well-know DNA sequence assembly problem. This newly developed algorithm is called DNA sequence assembly optimization. It first cuts any given DNA sequence into small fragments and then reassembles these fragments into a new sequence. The newly reassembled sequence can match gene engineering requirements for future bioinformatics developments. This DNA algorithm fully utilizes parallelism to conquer computation complexity bottleneck and can solve the DNA sequence assembly problem more efficient. Experimental results for DNA sequence assembly problem solving have shown in O(n^6) polynomial bound.

並列關鍵字

DNA csequence assembly ； NP-hard problem ； systems bioinformatics omputing ； optimization ； shotgun method ； parallelism

參考文獻

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

Blazewicz, J., Figlerowicz, M., Jackowiak, P., Janny, D., Jarczynski, D., Kasprzak, M., et al. (2004). Parallel DNA sequence assembly. Proceedings of the Fifth Mexican International Conference, 378 - 382

Braich, R. S., Johnson, C., Rothemund, P. W. K., Hwang, D., Chelyapov, N. V., & Adleman, L. M. (2001). Solution of a Satisfiability Problem on a Gel-Based DNA Computer. Paper presented at the Lecture Notes in Computer Science.

Burks, C. (1994). DNA sequence assembly. Engineering in Medicine and Biology Magazine, 13(5), 771-773.

Chang, W. L., Guo, M., & Ho, S. H. (2005). Fast parallel molecular algorithms for DNA-based computation: factoring integers. NanoBioscience, IEEE Transactions on, 4(2), 149-163.