关于系统发生树的星覆盖

《关于系统发生树的星覆盖》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、关于系统发生树的星覆盖Onstarcovetsofphylogenetictrees博士后姓名李强流动站(一级学科)名称上海生命科学研究院生物学专业(二级学科)名称计算生物学研究工作起始时间2009年7月研究工作期满时间2013年6月上海生命科学研究院2013年6月内容摘要给定若干物种两两之间的进化距离可以决定一棵系统发生树，这是进化生物学的一条基本定理。当部分距离信息缺失时，系统发生树仍有可能被唯一确定，但已知元素必须有足够“覆盖度”。最近的文献中猜测，“星覆盖”能够满足这一要求，即对给定系统发生树T上任一度为d的内部

2、结点u，都有一个子树T(可)，使得其中u的度数仍为d，且叶子结点两两之间的距离完全己知，则T能够被唯一重建。这里我们通过将覆盖表示为一个二分图，给出星覆盖的若干性质，及其能够唯一确定系统发生树的若干充分条件。我们证明叶结点数少于12的树均可从星覆盖唯一重建，并构建和分析了前述条件不能包含的若干星覆盖的特例。关键词：系统发生树，星覆盖，T确定集合系统，强套索AbstractAfundamentaltheoreminevolutionarybiologyisthataphyloge—netictreecanbedetermi

3、nedfromtheevolutionarydistancesbetweenspecies．Thetreemaybedeterminedevenwhensomedistancedataismissing，iftheknownelementsprovideenough“coverage”Itwascon—jecturedinarecentpaperthat“starcovers”satisfythiscondition，thatis，aphylogenetictreeTcanbeuniquelydeterminediffo

4、reachofitsinteriorvertexVwithdegreed，thereisasubtreeT(u)，ofwhichthedistancesbetweenleavesarecompletelyknown．Herewerepresentedsuchacoverbyabipartitegraph，characterizedsomeofitsproperties．andproposedsomesufficientconditionsforreconstructingphylogenetictrees．Weprove

5、dthatallphylogenetictreeswithlessthan12leavescailbeuniquelydeterminedbyitsstarcovers，andweconstructedexamplesofstarcoversoflargertrees．Keywords：PhylogeneticX—tree，starcover，T—definiteset,system，stronglaSSO．目次1引言2基本记号、定义和事实3丁确定集合系统4系统发生X树的星覆盖致谢参考文献个人简历博士生期间发表的学术论文

6、博士后期间发表的学术论文永久通信地址V1216567890；12341引言有限集合X上的度规D被称为一个树度规，如果存在叶子集合为X的树和非负边权，使得对X中所有元素z和Y，树上连接它们的路径的距离为D(x，可)．显然并非所有度规都是树度规，但当D确为树度规时，表示它的树连同边权是同构意义下唯一的。可是，重建这棵树并不需要知道所有(1夸1)对距离。因此研究(X。)的哪些子集足够确定这棵树看来是有意义的。这里我们仔细讨论此问题的若干方面，并提出一些相关定义。与此问题的提出有关的是基于距离的系统发生树构造，这在进化生物学中广

7、为应用(Felsenstein2004)．当涉及的物种数量众多时，通过一些“稀疏”的距离元素做推断是相当自然的考虑，这就是将若干已有的树组成较大的“超树”的方法。这里我们考虑理想的数学问题，即涉及到的距离均满足树度规，子树之间没有不一致的情况。同样背景之下已经引发了一些其他有趣的问题，包括数学、统计和算法方面。一般的从有缺失距离数据重构系统发生树构成矩阵补全问题，即使其可行性的判定也是NP复杂的问题。这里主要考虑一些重要的特殊情况。我们将(A．W．M．Dress，Huber，andSteel2012)中提出的三元组覆盖推

8、广到一般的系统发生X树上，即不要求它是二叉树，并为解决其中的主要猜想提出了可能的路线。在下一章中，我们给出若干定义并规定各种记号，以使得我们能够用数学语言讨论所涉及的问题。对若干概念详细给出了有关性质。第三章定义T确定集合系统并得到了它的许多性质。特别地，对只有两个被诱导子树的情况给出了完整的刻画。最后一章专门讨论星