【摘 要】
：
求解2个给定的系统发生树的最大一致森林问题在计算生物学上是一个非常重要的NP-难问题。系统发生树包括了有根和无根2种情况。本文主要研究无根多叉系统发生树。生物方面：最
论文部分内容阅读
求解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)的固定参数可解算法。
其他文献
油、气含量是指油气田勘探开发、确定投资与建设规模、评估油气田资源性资产的重要依据。然而，在油气田勘探初期，准确的储量数字是很难确定的，只能在一定的误差范围内估算地质储
近些年,车辆交通群组动画在各行各业得以广泛应用。关于交通模拟的研究也越来越引人注目,包括基于宏观特征和微观模型在内的许多新颖的模拟方法被提了出来。在某些实际应用中
移动自组网是在不需要预先部署任何基础设施的情况下,无线终端以随机的方式构成的一种分布式自组织网络环境,其本身的随机移动和动态拓扑特性给研究工作带来了新的挑战。解决
在自然科学和工程应用领域中存在大量约束优化问题,这些约束优化问题因常常含有多种不同类型的非线性约束条件、多模目标函数以及凹可行域而变得非常复杂。因此,对约束优化问
WSN节点一般部署在较为恶劣的环境中工作，由于不间断电源无法直接送达，网络中的节点大部分采用电池供电，节点一旦部署投入使用便很难再更换电池。在电池技术还没有获得突破性进
随着网民规模的不断扩大,网络环境和信息的安全问题也日益严重。域名系统DNS(Domain Name System的简称)作为保证整个互联网正常运行的网络基础设施,它的安全问题尤为重要。
近年来，车载自组网(Vehicular Ad Hoc Networks，VANETs)快速发展，其作为移动自组网(Mobile Ad Hoc Networks，MANETs)的一个特类，将车辆视作移动网络中的通信节点，用于节点之间以及
随着现代通信、计算机和传感器技术的迅速发展，具有感知、计算和通信能力的无线传感器网络(wireless sensor networks，WSN)应运而生。作为一种典型的普适计算的应用，WSN是大规模
随着计算机互联网技术和软件技术的发展,分布式应用越来越多,Web服务是当前构造分布式应用的标准框架。特别是SOA(面向服务的体系结构),云计算等技术的迅速发展,越来越多的企
Ad hoc网络是一个由具有无线通信功能的节点组成的多跳无线网络，由于其独有的自组织特性，使得Ad hoc网络适合需要临时架构网络的场所，在军事和民用等领域具有很大发展前景。