Combinatorial properties of triplet covers for binary trees
文献类型：期刊论文
| 作者 | Grunewald, Stefan1; Huber, Katharina T.2; Moulton, Vincent2; Steel, Mike3; , |
| 刊名 | ADVANCES IN APPLIED MATHEMATICS
 |
| 出版日期 | 2018 |
| 卷号 | 99期号:-页码:59-82 |
| 关键词 | Phylogenetic tree Triplet cover Tree-distances Hall's theorem Ample patchwork Shellability |
| ISSN号 | 0196-8858 |
| DOI | 10.1016/j.aam.2018.04.002 |
| 文献子类 | Article |
| 英文摘要 | It is a classical result that an unrooted tree T having positive real-valued edge lengths and no vertices of degree two can be reconstructed from the induced distance between each pair of leaves. Moreover, if each non-leaf vertex of T has degree 3 then the number of distance values required is linear in the number of leaves. A canonical candidate for such a set of pairs of leaves in T is the following: for each non-leaf vertex v, choose a leaf in each of the three components of T v, group these three leaves into three pairs, and take the union of this set over all choices of v. This forms a so-called 'triplet cover' for T. In the first part of this paper we answer an open question (from 2012) by showing that the induced leaf-to-leaf distances for any triplet cover for T uniquely determine T and its edge lengths. We then investigate the finer combinatorial properties of triplet covers. In particular, we describe the structure of triplet covers that satisfy one or more of the following properties of being minimal, 'sparse', and 'shellable'. (C) 2018 Elsevier Inc. All rights reserved. |
| 学科主题 | Mathematics |
| WOS关键词 | PHYLOGENETIC TREE |
| 语种 | 英语 |
| WOS记录号 | WOS:000434904100003 |
| 出版者 | ACADEMIC PRESS INC ELSEVIER SCIENCE |
| 版本 | 出版稿 |
| 源URL | [http://202.127.25.144/handle/331004/653]  |
| 专题 | 中国科学院上海生命科学研究院营养科学研究所 |
| 作者单位 | 1.Chinese Acad Sci, CAS MPG Partner Inst Computat Biol, Key Lab Computat Biol, Shanghai, Peoples R China; 2.Univ East Anglia, Sch Comp Sci, Norwich, Norfolk, England; 3.Univ Canterbury, Biomath Res Ctr, Christchurch, New Zealand, |
| 推荐引用方式 GB/T 7714 | Grunewald, Stefan,Huber, Katharina T.,Moulton, Vincent,et al. Combinatorial properties of triplet covers for binary trees[J]. ADVANCES IN APPLIED MATHEMATICS,2018,99(-):59-82. |
| APA | Grunewald, Stefan,Huber, Katharina T.,Moulton, Vincent,Steel, Mike,&,.(2018).Combinatorial properties of triplet covers for binary trees.ADVANCES IN APPLIED MATHEMATICS,99(-),59-82. |
| MLA | Grunewald, Stefan,et al."Combinatorial properties of triplet covers for binary trees".ADVANCES IN APPLIED MATHEMATICS 99.-(2018):59-82. |
入库方式： OAI收割
来源：上海营养与健康研究所
浏览0
下载0
收藏0
其他版本
除非特别说明，本系统中所有内容都受版权保护，并保留所有权利。