Abstract
In order to help infer an evolutionary tree (phylogeny) from experimental data, we propose a new method for pre-processing the corresponding dissimilarity matrix, which is related to the property that the distance matrix of a phylogeny (called an additive matrix) describes a sandwich family of chordal graphs. As experimental data often yield distance values which are known to be under-estimated, we address the issue of correcting the data by increasing the distances which are incorrect. This is done by computing, for each graph of the sandwich family, a maximal chordal subgraph.
This is a preview of subscription content, log in via an institution to check access.
Similar content being viewed by others
Explore related subjects
Discover the latest articles, news and stories from top researchers in related subjects.References
Balas E (1986) A fast algorithm for finding an edge-maximal subgraph with a TR-formative coloring. Discrete Appl Math 15:123–134
Barthélémy J-P, Guénoche A (1991) Trees and proximity representations. Wiley (eds), New York
Berry A (1999) A wide-range efficient algorithm for minimal triangulation. In: Proceedings of tenth annual ACM-SIAM symposium on discrete algorithms (SODA'99), 860–861
Berry A, Blair J, Heggernes P (2002) Maximum cardinality search for computing minimal triangulations. In: Kucera L (ed) Graph theoretical concepts in computer science – WG 2002, LNCS 2573, Springer Berlin Heidelberg New York 1–12
Berry A, Bordat J-P, Heggernes P (2000) Recognizing weakly triangulated graphs by edge separability. Nordic J Comput 7:164–177
Berry A, Heggernes P, Villanger Y (2003) An on-line incremental approach for dynamically maintaining chordal graphs. Research Report LIMOS: RR 2003-04
Berry A, Bordat J-P, Heggernes P, Simonet G, Villanger Y (2003) A wide-range algorithm for minimal triangulation from an arbitrary ordering. Technical report reports in informatics 243, University of Bergen (Norway); Research Report LIMOS: RR 2003-02. J Algorithms (submitted)
Berry A, Sigayret A, Sinoquet C (2002) Towards improving phylogeny reconstruction with combinatorial-based constraints on an underlying family of graphs. Research Report LIMOS: RR 02-103
Berry V, Gascuel O (2000) Inferring evolutionary trees with strong combinatorial evidence. Theor Comput Sci 240 2:271–298
Blair JRS, Peyton B (1993) An introduction to chordal graphs and clique trees. Graph Theory Sparse Matrix Comput 56:1–29
Bonnot F, Guénoche A, Perrier X (1996) Properties of an order distance associated with a tree distance. In: Diday E et al (eds) Proceedings of OSDA'95 (Ordinal and Symbolic Data Analysis), Springer Berlin Heidelberg New York 252–261
Brandstädt A, Le VB, Spinrad J (1999) Graph classes – a survey. SIAM monographs on discrete mathematics and applications
Buneman P (1971) The recovery of trees from measures of dissimilarity. Mathematics in the archeological and historical sciences. Edinburgh University Press, 387–395
Buneman P (1974) A characterization of rigid circuit graphs. Discrete Math 9:205–212
Coleman TF (1988) A chordal preconditioner for large-scale optimization. Appl Math 40:265–287
Dearing PM, Shier DR, Warner DD (1988) Maximal chordal subgraphs. Discrete Appl Math 20:181–190
Erdös P, Laskar R (1983) On maximum chordal subgraph. Cong Numerantium 39:367–373
Garetta H, Guénoche A (2001) How confident can we be that a tree representation is good? (Quelle confiance accorder à une représentation arborée?). In: Gascuel O, Sagot M-F (eds) Proceedings of JOBIM 2000, LNCS, vol 2066 Springer Berlin Heidelberg, New York pp 45–56
Gàvril F (1974) The intersection graphs of subtrees of trees are exactly the chordal graphs. J Comb Theory B, 16:47–56
Golumbic MC (1980) Algorithmic graph theory and perfect graphs. Academic Press New York
Guénoche A (1998) Ordinal properties of tree distances. Discrete Appl Math 192:103–117
Hayward R, Hoàng C, Maffray F (1989) Optimizing weakly triangulated graphs. Graphs Comb 5:339–349
Hein J (1989) An optimal algorithm to reconstruct trees from additive distance data. Bull Math Biol 51(5):597–603
Huson D, Nettles S, Warnow T (1999) Obtaining highly accurate topology estimates of evolutionary trees from very short sequences. In: Proceedings of RECOMB'99, Lyon (France), 198–207
Ibarra L (2000) Fully dynamic algorithms for chordal graphs and split graphs. Technical report, University of Victoria DCS-262-IR
Kearney P, Hayward R, Meijer H (1997) Inferring evolutionary trees from ordinal data. In: Proceedings of eighth annual ACM-SIAM symposium on Discrete Algorithms (SODA'97) 418–426
Rose D, Tarjan RE, Lueker G (1976) Algorithmic aspects of vertex elimination on graphs. SIAM J Comput 5:146–160
Spinrad J, Sritharan R (1995) Algorithms for weakly triangulated graphs. Discrete Appl Math 59:181–191
Walter JR (1978) Representations of Chordal Graphs as Subtrees of a Tree. J Graph Theory 2:265–267
Xue J (1994) Edge-maximal triangulated subgraphs and heuristics for the maximum clique problem. Networks 24:109–120
Author information
Authors and Affiliations
Corresponding author
Rights and permissions
About this article
Cite this article
Berry, A., Sigayret, A. & Sinoquet, C. Maximal sub-triangulation in pre-processing phylogenetic data. Soft Comput 10, 461–468 (2006). https://doi.org/10.1007/s00500-005-0507-7
Published:
Issue Date:
DOI: https://doi.org/10.1007/s00500-005-0507-7