PQ-樹(shù)斷點(diǎn)中心問(wèn)題算法研究與實(shí)現(xiàn).pdf

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

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

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

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