求解2个给定的系统发生树的最大一致森林问题在计算生物学上是一个非常重要的NP-难问题。系统发生树包括了有根和无根2种情况。
本文主要研究无根多叉系统发生树。生物方面：最近在生物和进化领域的研究文献表明经典的树搜索算法(例如：NNI算法)当在多叉的情况下会遇到不能解决的问题。
另外,生物文献在2006年提出计算无根多叉系统发生树的SPR距离,它的问题复杂性仍然是开放的。理论方面：无根多叉系统发生树是否可以固定参数可解被Hallett和McCartin在2007年作为开放问题而提出,随后Whidden等在2011年再次提出求解无根和有根多叉系统发生树是开放问题。
本文对多叉系统发生树中出现的新特征结构即星形quartet进行了研究。通过将2叉系统发生树中的蝴蝶quartet和星形quartet共同进行研究。
最终,将Hallett和McCartin只针对2叉系统发生树所提出的最小不兼容quartet结构推广到了一般情况即多叉系统发生树上,并且对扩展后产生的新问题进行了进一步的研究,首次提出了新特征结构冲突链。本文通过对上述2种特征结构的研究证明了求解无根多叉系统发生树的最大一致森林问题是固定参数可解的。
这样,本文解决了先前由Hallett, McCartin以及Whidden等提出的开放问题。最后,通过运用分支搜索技术,本文首次得到了时间复杂度为O(4kn5)的固定参数可解算法。
因篇幅问题不能全部显示，请点此查看更多更全内容