Approximations par arbre d'une distance partielle

Alain Guénoche; Stéphane Grandcolas

Mathématiques et Sciences Humaines (1999)

  • Volume: 146, page 51-64
  • ISSN: 0987-6936

Abstract

top
In tree clustering, we try to approximate a given dissimilarity matrice by a tree distance. In some cases, especially when comparing biological séquences, some dissimilarity values cannot be evaluated and we get some partial dissimilarity with undefined values. In that case one can develop a sequential method to reconstruct a valued tree or evaluate the missing values using a tree model. This paper introduces two methods of this kind and compare them simulating noisy partial tree dissimilarities.

How to cite

top

Guénoche, Alain, and Grandcolas, Stéphane. "Approximations par arbre d'une distance partielle." Mathématiques et Sciences Humaines 146 (1999): 51-64. <http://eudml.org/doc/94525>.

@article{Guénoche1999,
abstract = {En classification par arbre, on cherche à ajuster une dissimilarité donnée par une distance d'arbre. Mais bien souvent, surtout par comparaison de séquences biologiques, les valeurs obtenues sont peu fiables, voire indéterminées. On a alors une distance partielle qui n'est pas définie pour toute paire. Dans ce cas, on peut soit développer une méthode spécifique qui n'utilise que les valeurs disponibles, soit estimer les valeurs manquantes et utiliser une méthode classique pour reconstruire l'arbre. Cet article présente deux méthodes de ce type et les compare à l'aide de simulations sur des distances d'arbre partielles et bruitées.},
author = {Guénoche, Alain, Grandcolas, Stéphane},
journal = {Mathématiques et Sciences Humaines},
keywords = {tree reconstruction; partial distance; sequential method},
language = {fre},
pages = {51-64},
publisher = {Ecole des hautes-études en sciences sociales},
title = {Approximations par arbre d'une distance partielle},
url = {http://eudml.org/doc/94525},
volume = {146},
year = {1999},
}

TY - JOUR
AU - Guénoche, Alain
AU - Grandcolas, Stéphane
TI - Approximations par arbre d'une distance partielle
JO - Mathématiques et Sciences Humaines
PY - 1999
PB - Ecole des hautes-études en sciences sociales
VL - 146
SP - 51
EP - 64
AB - En classification par arbre, on cherche à ajuster une dissimilarité donnée par une distance d'arbre. Mais bien souvent, surtout par comparaison de séquences biologiques, les valeurs obtenues sont peu fiables, voire indéterminées. On a alors une distance partielle qui n'est pas définie pour toute paire. Dans ce cas, on peut soit développer une méthode spécifique qui n'utilise que les valeurs disponibles, soit estimer les valeurs manquantes et utiliser une méthode classique pour reconstruire l'arbre. Cet article présente deux méthodes de ce type et les compare à l'aide de simulations sur des distances d'arbre partielles et bruitées.
LA - fre
KW - tree reconstruction; partial distance; sequential method
UR - http://eudml.org/doc/94525
ER -

References

top
  1. Barthélemy, J.P., Guénoche, A., Les arbres et les représentations des proximités, Collection "Méthodes et Programmes", Masson, 1988, Trees and Proximity Representations, J. Wiley,1991. 
  2. Buneman, P., "The recovery of trees from measures of dissimilarity", Mathematics in Archaeological and Historical Sciences, F.H. Hodson, D.G. Kendall, P. Tautu (Eds.), Edimburg University Press, (1971), 387-395. 
  3. De Soete, G., "Ultrametric tree representations of incomplete dissimilarity data ", J. of Classification, 1, (1984), 235-242. 
  4. De Soete, G., "Additive-tree representations of incomplete dissimilarity data", Qual. Quantity, 18, (1984), 387-393. 
  5. Duret, L., Mouchiroud, D., Gouy, M., "Hovergen : a database of homologous vertebrate genes", Nucleic Acids Res., 22, (1994), 2360-2365. 
  6. Gascuel, O., "Concerning the NJ Algorithm and its Unweighted Version, UNJ", Mathematical Hierarchies and Biology, B. Mirkin et al. (Eds.), DIMACS Series Discrete Mathematics and Theoretical Computer Science37, AMS, (1997), 149-170. Zbl0933.92026MR1600536
  7. Guénoche, A., Leclerc, B., "La méthode des triangles pour reconstruire un arbre à partir de distances incomplètes", Actes des Journées de la Société Francophone de Classification, Agro-Montpellier, (1998), 117-120. 
  8. Guénoche, A., Leclerc, B., "The triangles method to build phylogenetic trees from incomplete distance matrices", soumis à publication, (1998), 18 p. Zbl0992.05036
  9. Lapointe, F.J., Kirsch, J.A.W., "Estimating phylogenies from lacunose distances matrices : Additive is superior to Ultrametric estimation", Molecular Biology Evolution, 13(6), (1996), 266-284. 
  10. Leclerc, B., "La méthode de dispersion", communication personnelle (1986). Voir Barthélemy, J.-P. & Guénoche, A., p. 74 (1988) & p. 73 (1991). 
  11. Leclerc, B., "Minimum spanning trees for tree metrics : abridgements and adjustments ", J. of Classification, 12, (1995), 207-241. Zbl0845.62046MR1379502
  12. Leclerc, B., Makarenkov, V., "On some relations between 2-trees and tree metrics", DiscreteMath., 192, (1998), 223-249. Zbl0958.05029MR1656734
  13. Makarenkov, V., Leclerc, B., "The fitting of a tree metric to a given dissimilarity with the weighted least squares crterion", Journal of Classification, (1999), 223-249. MR1656734
  14. Robinson, D.R., Foulds, L.R., "Comparison of phylogenetic trees", Mathematical Biosciences, 53, (1981), 131-147. Zbl0451.92006MR613619
  15. Saitou, N., Nei, M., "The neighbor-joining method: a new method for reconstructing phylogenetic trees", Molecular Biology Evolution, 4, (1987), 406-425. 
  16. Studier, J.A., Keppler, K.J., "A note on the neighbor-joining method of Saitou and Nei", Molecular Biology Evolution, 5, (1988), 729-731. 
  17. Zaretskii, K., "Construction d'un arbre sur la base d'un ensemble de distances entre ses feuilles" (en russe), Uspekhi Mat. Nauk., 20, (1965), 90-92. Zbl0151.33302
  18. Waterman, M.S., Smith, T.F., Singh, M., Beyer, W.A., "Additive Evolutionary Trees", Journal of Theoretical Biology, 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.