# The triangles method to build X-trees from incomplete distance matrices

RAIRO - Operations Research (2010)

- Volume: 35, Issue: 2, page 283-300
- ISSN: 0399-0559

## Access Full Article

top## Abstract

top## How to cite

topGuénoche, Alain, and Leclerc, Bruno. "The triangles method to build X-trees from incomplete distance matrices." RAIRO - Operations Research 35.2 (2010): 283-300. <http://eudml.org/doc/116595>.

@article{Guénoche2010,

abstract = {
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.
},

author = {Guénoche, Alain, Leclerc, Bruno},

journal = {RAIRO - Operations Research},

keywords = {X-tree; partial distances; 2-trees.; valued trees; distance arrays; twotree; spanning tree},

language = {eng},

month = {3},

number = {2},

pages = {283-300},

publisher = {EDP Sciences},

title = {The triangles method to build X-trees from incomplete distance matrices},

url = {http://eudml.org/doc/116595},

volume = {35},

year = {2010},

}

TY - JOUR

AU - Guénoche, Alain

AU - Leclerc, Bruno

TI - The triangles method to build X-trees from incomplete distance matrices

JO - RAIRO - Operations Research

DA - 2010/3//

PB - EDP Sciences

VL - 35

IS - 2

SP - 283

EP - 300

AB -
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.

LA - eng

KW - X-tree; partial distances; 2-trees.; valued trees; distance arrays; twotree; spanning tree

UR - http://eudml.org/doc/116595

ER -

## References

top- Barthélemy J.P. and Guénoche A., Trees and proximities representations. J. Wiley, Chichester, UK (1991). Zbl0790.05021
- 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.
- Duret L., Mouchiroud D. and Gouy M., HOVERGEN: A database of homologous vertebrate genes. Nucleic Acids Res.22 (1994) 2360-2365.
- Farris J.S., Estimating phylogenetic trees from distance matrices. Amer. Nat.106 (1972) 645-668.
- 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.
- 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.
- 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. Zbl0886.05051
- Guénoche A. and S. Grandcolas S., Approximation par arbre d'une distance partielle. Math. Inform. Sci. Humaines146 (1999) 51-64.
- Harary F. and Palmer E.M., On acyclical simplicial complexes. Mathematika15 (1968) 115-122. Zbl0157.54903
- Hein J.J., An optimal algorithm to reconstruct trees from additive distance data. Bull. Math. Biol.51 (1989) 597-603. Zbl0674.92003
- 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.
- Leclerc B., Minimum spanning trees for tree metrics: Abridgements and adjustments. J. Classification12 (1995) 207-241. Zbl0845.62046
- Leclerc B. and Makarenkov V., On some relations between 2-trees and tree metrics. Discrete Math.192 (1998) 223-249. Zbl0958.05029
- Makarenkov V., Propriétés combinatoires des distances d'arbre : algorithmes et applications. Thèse de l'EHESS, Paris (1997).
- 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.
- Prim R.C., Shortest connection network and some generalizations. Bell System Tech. J.26 (1957) 1389-1401.
- Proskurowski A., Separating subgraphs in k-trees: Cables and caterpillars. Discrete Math.49 (1984) 275-295. Zbl0543.05041
- Robinson D.R. and Foulds L.R., Comparison of phylogenetic trees. Math. Biosci.53 (1981) 131-147. Zbl0451.92006
- Rose D.J., On simple characterizations of k-trees. Discrete Math.7 (1974) 317-322. Zbl0285.05128
- Saitou N. and Nei M., The neighbor-joining method: A new method for reconstructing phylogenetic trees. Mol. Biol. Evol.4 (1987) 406-425.
- Todd P., A k-tree generalization that characterizes consistency of dimensioned engineering drawings. SIAM J. Discete Math.2 (1989) 255-261. Zbl0684.05017
- Waterman M.S., Smith T.F., Singh M. and Beyer W.A., Additive Evolutionary Trees. J. Theor. Biol.64 (1977) 199-213.

## NotesEmbed ?

topTo embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.