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

Alain Guénoche; Bruno Leclerc

RAIRO - Operations Research - Recherche Opérationnelle (2001)

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

Abstract

top
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 2 n -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 .

How to cite

top

Guénoche, Alain, and Leclerc, Bruno. "The triangles method to build $X$-trees from incomplete distance matrices." RAIRO - Operations Research - Recherche Opérationnelle 35.2 (2001): 283-300. <http://eudml.org/doc/105247>.

@article{Guénoche2001,
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 2$n$-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 - Recherche Opérationnelle},
keywords = {X-tree; partial distances; 2-trees; valued trees; distance arrays; twotree; spanning tree},
language = {eng},
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/105247},
volume = {35},
year = {2001},
}

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 - Recherche Opérationnelle
PY - 2001
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 2$n$-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/105247
ER -

References

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

NotesEmbed ?

top

You must be logged in to post comments.

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

Only the controls for the widget will be shown in your chosen language. Notes will be shown in their authored language.

Tells the widget how many notes to show per page. You can cycle through additional notes using the next and previous controls.

    
                

                
Note: Best practice suggests putting the JavaScript code just before the closing </body> tag.