多叉系統(tǒng)發(fā)生樹最大一致森林問(wèn)題的研究.pdf

1、求解2個(gè)給定的系統(tǒng)發(fā)生樹的最大一致森林問(wèn)題在計(jì)算生物學(xué)上是一個(gè)非常重要的Np-難問(wèn)題。系統(tǒng)發(fā)生樹包括了有根和無(wú)根2種情況。本文主要研究無(wú)根多叉系統(tǒng)發(fā)生樹。生物方面:最近在生物和進(jìn)化領(lǐng)域的研究文獻(xiàn)表明經(jīng)典的樹搜索算法（例如:NNI算法）當(dāng)在多叉的情況下會(huì)遇到不能解決的問(wèn)題。另外，生物文獻(xiàn)在2006年提出計(jì)算無(wú)根多叉系統(tǒng)發(fā)生樹的SPR距離，它的問(wèn)題復(fù)雜性仍然是開放的。理論方面:無(wú)根多叉系統(tǒng)發(fā)生樹是否可以固定參數(shù)可解被Hallett和McCa

2、rtin在2007年作為開放問(wèn)題而提出，隨后Whidden等在2011年再次提出求解無(wú)根和有根多叉系統(tǒng)發(fā)生樹是開放問(wèn)題。
　　 本文對(duì)多叉系統(tǒng)發(fā)生樹中出現(xiàn)的新特征結(jié)構(gòu)即星形quartet進(jìn)行了研究。通過(guò)將2叉系統(tǒng)發(fā)生樹中的蝴蝶quartet和星形quartet共同進(jìn)行研究。最終，將Hallett和McCartin只針對(duì)2叉系統(tǒng)發(fā)生樹所提出的最小不兼容quartet結(jié)構(gòu)推廣到了一般情況即多叉系統(tǒng)發(fā)生樹上，并且對(duì)擴(kuò)展后產(chǎn)生的新問(wèn)題進(jìn)