計(jì)算生物學(xué)中若干組合優(yōu)化問題的研究.pdf

1、本文主要研究了計(jì)算分子生物學(xué)中的若干組合優(yōu)化問題.全文共分為六章.在論文的第一章里，首先簡要介紹了組合優(yōu)化，計(jì)算生物學(xué)問題，算法和時(shí)間復(fù)雜性等基本概念. 第二章主要研究了單個(gè)基因組序列的重排列問題.我們提出一種更具有一般性意義的新移位操作，并且設(shè)計(jì)出利用逆序和這種新移位操作對單染色體基因組重排列的近似算法. 第三章主要研究多染色體中基因組重定位問題.針對多染色體基因組重定位的一類松弛問題，稱作Syntenic距離問題，我

2、們提出一個(gè)新的特殊可解情形，稱為無覆蓋特殊類，并且設(shè)計(jì)出了相應(yīng)的多項(xiàng)式時(shí)間最優(yōu)算法. 第四章研究了染色體DNA序列重組合問題.我們研究這類問題的多項(xiàng)式時(shí)間特殊可解結(jié)構(gòu).我們針對一類“樹型”結(jié)構(gòu)，指出解這類特殊結(jié)構(gòu)的已有算法的不完備性，并且對重組“樹型”結(jié)構(gòu)進(jìn)行了更加全面的考慮，設(shè)計(jì)出新的算法，并嚴(yán)格證明了新算法的最優(yōu)性.在這一章中，我們還將新提出一類DNA序列的特殊可解結(jié)構(gòu)——“鏈型”結(jié)構(gòu)，設(shè)計(jì)出了最優(yōu)算法，實(shí)現(xiàn)了向“鏈型”結(jié)構(gòu)

3、DNA序列重組合的最優(yōu)演變過程. 在第五章里，我們重點(diǎn)討論DNA序列重組合中，“鏈型”結(jié)構(gòu)重組合問題的推廣.我們將第四章中所提出的“鏈型”結(jié)構(gòu)的限制性條件放寬了，提出了更具普遍意義下的“廣義鏈型”結(jié)構(gòu)，分若干情形討論了重組合“廣義鏈型”結(jié)構(gòu)的最優(yōu)過程，并且設(shè)計(jì)了最優(yōu)算法實(shí)現(xiàn)這一過程. 第六章主要研究了決定生物性狀的基因組群試問題.我們建立了決定生物性狀的基因組群試模型，即超圖上的群試問題，并且首次提出了一個(gè)求解該問題的競