×

The triangles method to build \(X\)-trees from incomplete distance matrices. (English) Zbl 0992.05036

The main result of this paper is a method of time complexity \(O(n^3)\) to infer valued trees having \(X\) as set of leaves from incomplete distance arrays. It allows the building of an unrooted tree using only \(2n-3\) distance values between the \(n\) elements of \(X\), if they fulfill some explicit conditions and it is based upon a weighted generalized 2-tree spanning \(X\), called twotree, which is a 2-connected graph of order \(n\) and size \(n-3\). Also, a method allowing one to recover an \(X\)-tree from a reduced set of pairwise distances between taxa and a greedy algorithm for the construction of a twotree which is an analogue of Prim’s algorithm for the shortest spanning tree are proposed.

MSC:

05C12 Distance in graphs
05C05 Trees

Software:

BIONJ
PDFBibTeX XMLCite
Full Text: DOI Numdam EuDML

References:

[1] Barthélemy J.P. and Guénoche A. , Trees and proximities representations . J. Wiley, Chichester, UK ( 1991 ). MR 1138723 | Zbl 0790.05021 · Zbl 0790.05021
[2] Buneman P. , The recovery of trees from measures of dissimilarity , edited by F.R. Hodson, D.G. Kendall and P. Tautu, Mathematics in Archaeological and Historical Sciences. Edinburg University Press, Edinburg ( 1971 ) 387 - 395 .
[3] Duret L. , Mouchiroud D. and Gouy M. , HOVERGEN: A database of homologous vertebrate genes . Nucleic Acids Res. 22 ( 1994 ) 2360 - 2365 .
[4] Farris J.S. , Estimating phylogenetic trees from distance matrices . Amer. Nat. 106 ( 1972 ) 645 - 668 .
[5] Gascuel O. , A note on Sattah and Tversky’s , Saitou and Nei’s and Studier and Keppler’s algorithms for inferring phylogenies from evolutionary distances. Mol. Biol. Evol. 11 ( 1994 ) 961 - 963 .
[6] Gascuel O. , BIONJ: An improved version of the NJ algorithm based on a simple model of sequence data . Mol. Biol. Evol. 14 ( 1997 ) 685 - 695 .
[7] Guénoche A. , Order distances in tree reconstruction , edited by B. Mirkin et al., Mathematical Hierarchies and Biology. American Mathematical Society, Providence, RI, DIMACS Ser. Discrete Math. Theoret. Comput. Sci. 37 ( 1997 ) 171 - 182 . MR 1600540 | Zbl 0886.05051 · Zbl 0886.05051
[8] Guénoche A. and S. Grandcolas S ., Approximation par arbre d’une distance partielle. Math. Inform. Sci. Humaines 146 (1999) 51-64. Numdam
[9] Harary F. and Palmer E.M. , On acyclical simplicial complexes . Mathematika 15 ( 1968 ) 115 - 122 . MR 228355 | Zbl 0157.54903 · Zbl 0157.54903 · doi:10.1112/S002557930000245X
[10] Hein J.J. , An optimal algorithm to reconstruct trees from additive distance data . Bull. Math. Biol. 51 ( 1989 ) 597 - 603 . Zbl 0674.92003 · Zbl 0674.92003 · doi:10.1007/BF02459968
[11] Lapointe F.J. and Kirsch J.A.W. , Estimating phylogenies from lacunose distance matrices: Additive is superior to ultrametric estimation . Mol. Biol. Evol. 13 ( 1996 ) 266 - 284 .
[12] Leclerc B. , Minimum spanning trees for tree metrics: Abridgements and adjustments . J. Classification 12 ( 1995 ) 207 - 241 . MR 1379502 | Zbl 0845.62046 · Zbl 0845.62046 · doi:10.1007/BF03040856
[13] Leclerc B. and Makarenkov V. , On some relations between 2-trees and tree metrics . Discrete Math. 192 ( 1998 ) 223 - 249 . MR 1656734 | Zbl 0958.05029 · Zbl 0958.05029 · doi:10.1016/S0012-365X(98)00073-9
[14] Makarenkov V. , Propriétés combinatoires des distances d’arbre : algorithmes et applications . Thèse de l’EHESS, Paris ( 1997 ).
[15] Pippert R.E. and Beineke L.W. , Characterisation of 2-dimentional trees , edited by G. Chatrand and S.F. Kapoor, The Many Facets of Graph Theory. Springer-Verlag, Berlin, Lecture Notes in Math. 110 ( 1969 ) 263 - 270 . MR 252271 | Zbl 0186.27801 · Zbl 0186.27801
[16] Prim R.C. , Shortest connection network and some generalizations . Bell System Tech. J. 26 ( 1957 ) 1389 - 1401 .
[17] Proskurowski A. , Separating subgraphs in \(k\)-trees: Cables and caterpillars . Discrete Math. 49 ( 1984 ) 275 - 295 . MR 743798 | Zbl 0543.05041 · Zbl 0543.05041 · doi:10.1016/0012-365X(84)90164-X
[18] Robinson D.R. and Foulds L.R. , Comparison of phylogenetic trees . Math. Biosci. 53 ( 1981 ) 131 - 147 . MR 613619 | Zbl 0451.92006 · Zbl 0451.92006 · doi:10.1016/0025-5564(81)90043-2
[19] Rose D.J. , On simple characterizations of \(k\)-trees . Discrete Math. 7 ( 1974 ) 317 - 322 . MR 335319 | Zbl 0285.05128 · Zbl 0285.05128 · doi:10.1016/0012-365X(74)90042-9
[20] Saitou N. and Nei M. , The neighbor-joining method: A new method for reconstructing phylogenetic trees . Mol. Biol. Evol. 4 ( 1987 ) 406 - 425 .
[21] Todd P. , A \(k\)-tree generalization that characterizes consistency of dimensioned engineering drawings . SIAM J. Discete Math. 2 ( 1989 ) 255 - 261 . MR 990455 | Zbl 0684.05017 · Zbl 0684.05017 · doi:10.1137/0402022
[22] Waterman M.S. , Smith T.F. , Singh M. and Beyer W.A. , Additive Evolutionary Trees . J. Theor. Biol. 64 ( 1977 ) 199 - 213 . MR 503996
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.