PQ-樹斷點中心問題算法研究與實現(xiàn).pdf

1、計算生物學(xué)是一門綜合性很強(qiáng)的學(xué)科，它涉及到生物學(xué)、計算機(jī)科學(xué)等多種內(nèi)容。根據(jù)達(dá)爾文的生物進(jìn)化論，普遍認(rèn)為物種之間存在一種遺傳系譜關(guān)系，為了生動形象的描述物種之間的遺傳系譜關(guān)系，科學(xué)家們提出了生物進(jìn)化樹。生物進(jìn)化樹是一種樹狀圖表，在生物進(jìn)化樹的分支上，存放的是能代表不同物種的結(jié)構(gòu)或者信息。但在構(gòu)建生物進(jìn)化樹時，采用何種信息來代表生物物種是值得人類思考的問題，現(xiàn)在普遍認(rèn)可采用基因組序列代表對應(yīng)物種來構(gòu)建生物進(jìn)化樹。
　　伴著生物實驗水

2、平的提升，人們利用各種實驗手段得到了大量的基因組數(shù)據(jù)，這些基因組數(shù)據(jù)對于研究生物進(jìn)化史有著不可或缺的作用。鑒于此，科學(xué)家們提出了利用基因組數(shù)據(jù)來作為生物進(jìn)化樹的構(gòu)成元素。
　　在構(gòu)建生物進(jìn)化樹時，要根據(jù)不同物種基因組序列的相似程度來衡量基因組序列所對應(yīng)物種之間的親緣關(guān)系的遠(yuǎn)近。對于祖先物種基因組，由于祖先物種已經(jīng)消逝，人類無法得到祖先物種完整基因組，只能利用現(xiàn)有技術(shù)得到祖先物種基因組片段，推測祖先物種基因組中的連續(xù)遺傳區(qū)。因此，在

3、存儲祖先物種基因組時，要考慮祖先物種基因組的特點，本文利用PQ-樹可以表示排列的集合的特性，采用PQ-樹來存儲祖先物種基因組，而對于現(xiàn)有物種基因組，則用排列表示。
　　不同物種之間的同源性與物種基因組序列的相似程度有著極大的關(guān)系，因此，可以通過比較不同物種基因組序列之間的相似程度，從而了解物種的進(jìn)化。在衡量不同物種基因組序列的相似程度時，利用序列比對的方法來判定基因組序列之間的差異。在基因組序列比較時，要有一定的標(biāo)準(zhǔn)來量化基因組序

4、列之間的相似程度，本文中，將以斷點距離為標(biāo)準(zhǔn)，衡量物種基因組序列的相似程度。
　　在生物進(jìn)化樹中，葉子結(jié)點表示現(xiàn)有物種基因組，本文中采用排列表示，內(nèi)部結(jié)點表示祖先物種基因組，本文采用PQ-樹結(jié)構(gòu)存儲，鑒于祖先物種基因組與現(xiàn)有物種基因組基本組成元素相同，因此PQ-樹中葉子結(jié)點所表示的元素與排列中含有的元素也相同。為了判斷祖先物種與現(xiàn)有物種之間的進(jìn)化關(guān)系，需要衡量祖先物種基因組與現(xiàn)有物種基因組之間的相似程度，即需要求解PQ-樹所表示的