论文部分内容阅读
组合数学和图论由于其在计算机、人工智能和通信领域的广泛应用,赢得了越来越多的重视和研究。人们也渐渐认识到好的算法离不开好的组合图论分析。 生物学中一个重要的研究方向是探讨在历史发展过程中生物种系的发生和发展。通过各种实验数据(如DNA序列)的分析,人们就可以为生物物种建立一棵系统发生树£演化树),并由它来描述各个物种之间可能有的亲缘联系和发展演进过程。由于这些实验数据不总是那么精确(如从化石中得来的数据常常并不完整),因此若研究的侧重点不同会导致恢复出来的系统发生树也不唯一。而且由于系统发生的进化过程是不能被直接通过观察和实验所证实的,因此给研究人员带来的课题是如何确定正确的系统发生树。研究人员发现通过数学的方法特别是组合图论的理论可以帮助更精确地恢复出系统发生树,因此逐渐形成了系统发生组合学这个研究分支。系统发生组合学的研究也可以运用于许多领域的算法设计研究,这些领域包含网络结构的比较、从已有的信息来恢复网络的结构等。 T-Theory是系统发生学中一个重要方向,Tight Span和Split Decomposition理论是其两大主要内容。文章总结了T-Theory理论的经典结论以及一些最新研究进展,也包含我们自己在Tight Span和Split Decomposition理论框架中的新研究结果。这些新工作包括: ⑴在Tight Span章节扩展了原始的度量意义下的Tight Span理论得到了子树长度意义的Tight Span结论; (2)在Split分解章节揭示了Split分解从Metric到Tree Metric再到Totally Decomposable Metric之间的联系与发展,在此基础上还分析了更普遍的双曲率概念与Split分解理论之间的结合联系; (3)为了达到理论与实际相结合的目的,文章还包含了Splits Tool应用工具的简单介绍以及相应的系统发生树重构实例,Split理论在量化比较树结构等方面的应用在文章中也有所涉及。