The triangles method to build X-trees from incomplete distance matrices
RAIRO - Operations Research - Recherche Opérationnelle, Tome 35 (2001) no. 2, pp. 283-300.

On décrit une méthode pour la reconstruction des X-arbres (arbres valués admettant X comme ensemble de feuilles) à partir de tableaux de distances incomplets (où certaines valeurs sont incertaines ou inconnues). Elle permet de construire un arbre non orienté à partir de 2n-3 valeurs de distance entre les n éléments de X, sous des conditions qui sont explicitées. Cette construction est basée sur une relation entre X-arbres et 2-arbres valués généralisés d’ensemble de sommets X.

A method to infer X-trees (valued trees having X as set of leaves) from incomplete distance arrays (where some entries are uncertain or unknown) is described. It allows us to build an unrooted tree using only 2n-3 distance values between the n elements of X, if they fulfill some explicit conditions. This construction is based on the mapping between X-tree and a weighted generalized 2-tree spanning X.

Mots clés : X-tree, partial distances, 2-trees
     author = {Gu\'enoche, Alain and Leclerc, Bruno},
     title = {The triangles method to build $X$-trees from incomplete distance matrices},
     journal = {RAIRO - Operations Research - Recherche Op\'erationnelle},
     pages = {283--300},
     publisher = {EDP-Sciences},
     volume = {35},
     number = {2},
     year = {2001},
     zbl = {0992.05036},
     mrnumber = {1868873},
     language = {en},
     url = {}
Guénoche, Alain; Leclerc, Bruno. The triangles method to build $X$-trees from incomplete distance matrices. RAIRO - Operations Research - Recherche Opérationnelle, Tome 35 (2001) no. 2, pp. 283-300.

[None] Barthélemy J.P. and Guénoche A., Trees and proximities representations. J. Wiley, Chichester, UK (1991). | MR 1138723 | Zbl 0790.05021

[None] 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.

[None] Duret L., Mouchiroud D. and Gouy M., HOVERGEN: A database of homologous vertebrate genes. Nucleic Acids Res. 22 (1994) 2360-2365.

[None] Farris J.S., Estimating phylogenetic trees from distance matrices. Amer. Nat. 106 (1972) 645-668.

[None] 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.

[None] 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.

[None] 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

[None] Guénoche A. and S. Grandcolas S., Approximation par arbre d'une distance partielle. Math. Inform. Sci. Humaines 146 (1999) 51-64. | Numdam

[None] Harary F. and Palmer E.M., On acyclical simplicial complexes. Mathematika 15 (1968) 115-122. | MR 228355 | Zbl 0157.54903

[None] Hein J.J., An optimal algorithm to reconstruct trees from additive distance data. Bull. Math. Biol. 51 (1989) 597-603. | Zbl 0674.92003

[None] 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.

[None] Leclerc B., Minimum spanning trees for tree metrics: Abridgements and adjustments. J. Classification 12 (1995) 207-241. | MR 1379502 | Zbl 0845.62046

[None] 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

[None] Makarenkov V., Propriétés combinatoires des distances d'arbre : algorithmes et applications. Thèse de l'EHESS, Paris (1997).

[None] 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

[None] Prim R.C., Shortest connection network and some generalizations. Bell System Tech. J. 26 (1957) 1389-1401.

[None] Proskurowski A., Separating subgraphs in k-trees: Cables and caterpillars. Discrete Math. 49 (1984) 275-295. | MR 743798 | Zbl 0543.05041

[None] Robinson D.R. and Foulds L.R., Comparison of phylogenetic trees. Math. Biosci. 53 (1981) 131-147. | MR 613619 | Zbl 0451.92006

[None] Rose D.J., On simple characterizations of k-trees. Discrete Math. 7 (1974) 317-322. | MR 335319 | Zbl 0285.05128

[None] Saitou N. and Nei M., The neighbor-joining method: A new method for reconstructing phylogenetic trees. Mol. Biol. Evol. 4 (1987) 406-425.

[None] 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

[None] Waterman M.S., Smith T.F., Singh M. and Beyer W.A., Additive Evolutionary Trees. J. Theor. Biol. 64 (1977) 199-213. | MR 503996