New Metrics for Phylogenies

• Autorzy: Bolikowski, Ł. , Gambin, A.
• Języki publikacji: EN

Abstrakty

EN

In this paper we propose two new metrics defined on the space of phylogenetic trees. The problem of determining how distant two trees are from each other is crucial because many various methods exist for reconstructing phylogenetic trees from molecular data. These techniques (in fact often heuristics) applied to the same data set result in significantly different trees. We investigate the basic properties of new metrics and present efficient algorithms approximating the distance between two trees for partition metric. Computational experiments, which has been performed for large family of trees justify the applicability of our algorithms. The interesting application of our framework is the identification of the ancestral paralog position in the paralog families. We propose to select the set of genes (exemplars) that minimize the partition metric distance between gene tree and species tree.

Słowa kluczowe

EN

new metrics

• Czasopismo: Fundamenta Informaticae
• Rocznik: 2007
• Tom: Vol. 78, nr 2
• Strony: 199-216
• Opis fizyczny: bibliogr. 22 poz., tab., wykr.

Twórcy

autor

Bolikowski, Ł.

autor

Gambin, A.

• Institute of Informatics University of Warsaw ul. Banacha 2, 02-097 Warsaw, Poland,

Bibliografia

• [1] Aho A. V. et. al (1981), Inferring a tree fromlowest common ancestorswith an application to the optimization o relational expressions, SIAM Journal of Computing, 10(3):405-421.
• [2] Allen B. L., Steel M. (2001), Subtree Transfer Operations and their Induced Metrics on Evolutionary Trees Annals of Combinatorics 5:1-13.
• [3] Bourque, G., Yacef, Y., El-Mabrouk, N. (2005), Maximizing synteny blocks to identify ancestral homologs. In Proc. of RECOMB Comparative Genomics Satellite Workshop, LNBI 3678:21-34.
• [4] Bryant D. (1997), Building trees, hunting for trees, and comparing trees, Ph.D. thesis, University of Canterbury, New Zealand.
• [5] DasGupta B. et al. (2000), On computing the nearest neighbor interchange distance, DIMACS Ser. Discrete Math. Theoret. Comput. Sci., 55:125-143, Amer. Math. Soc., Providence, RI
• [6] Daubin, V., Gouy, M., Perriere, G. (2002) A Phylogenomic Approach to Bacterial Phylogeny: Evidence of a Core of Genes Sharing a Common History, Genome Research, Vol. 12, Issue 7, 1080-1090.
• [7] Gambin A., Lasota S., Szklarczyk R., Tiuryn J., Tyszkiewicz J. (2002), Contextual Alignment of Biological Sequences, Proc. ECCB'02, Bioinformatics 18:116-127, Oxford University Press.
• [8] Gambin, A., Tiuryn J., Tyszkiewicz, J. (2006) Alignment with context dependent scoring function, Journal of Computational Biology,13(1):81-101.
• [9] Gambin A., Slonimski P. P. (2005), Hierarchical clustering based upon contextual alignment of proteins: a different way to approach phylogeny, C.R. Biologie Acad. Science Paris, 328:11-22.
• [10] Kubicka, E., Kubicki, G., McMorris, F.R. (1995), An algorithm to find agreement subtrees, Journal of Classification,12:91-99.
• [11] Li,M., Tromp, J., Zhang, L. (1995), On the nearest neighbor interchange distance between evolutionary trees. J. Theor. Biol. 182:463-467.
• [12] Li, W-H. (1997), Molecular Evolution,Sinauer Associates.
• [13] R. Page, Component, tree comparison software, The Natural History Museum, London.
• [14] Page R. D. M., Holmes E. C. (1998), Molecular Evolution: A phylogenetic approach, Blackwell Scientific, Oxford.
• [15] Robinson, D.F., Foulds, L.R. (1981) Comparison of phylogenetic trees, Math. Biosci.53:131-147.
• [16] Rodrigues E. M., Sagot M-F. and Wakabayashi Y. (2001), Some approximation results for the maximum agreement forest problem, in Proc. APPROX and RANDOM'01 LNCS, vol. 2129:159-169.
• [17] Sankoff, D. (1999), Genome rearrangement with gene families, Bioinformatics Vol. 15 no. 11, 909-917.
• [18] Steel M, McKenzie A. (2001), Properties of phylogenetic trees generated by Yule-type speciation models. Math Biosci. 2001 Mar;170(1):91-112.
• [19] Steel, M.A. and Penny, D.(1993), Distributions of tree comparison metrics - some new results. Systematic Biology, 42(2): 126-141.
• [20] D. H. Huson and M. Steel. (2004), Distances that perfectly mislead, Systematic Biology 53(2): 327-332.
• [21] Steel M., Warnow T. (1993), Kaikoura Tree Theorems: Computing the Maximum Agreement Subtree, Inf. Process. Lett. 48(2): 77-82.
• [22] Tatusov R. L. et al (2001), The COG database: new developments in phylogenetic classification of proteins from complete genomes, Nucleic Acids Res., 21(1):22-28.