Metoda porównywania drzew filogenetycznych wykorzystująca najlżejsze doskonałe skojarzenie w grafach dwudzielnych

• Autorzy: Bogdanowicz D.

Warianty tytułu

EN

Comparing phylogenetic trees using a minimum weight perfect matching

• Języki publikacji: PL

Abstrakty

PL

Drzewa filogenetyczne przedstawiają historyczne, ewolucyjne związki pokrewieństwa między różnymi gatunkami lub różnymi osobnikami w ramach jednego gatunku. Istnieje wiele metod rekonstruowania drzew filogenetycznych. Wykorzystywanie różnych metod na tym samym zbiorze danych zazwyczaj owocuje powstaniem różnych drzew. Pojawia się zatem pytanie: jak bardzo dwa dane drzewa różnią się od siebie. W niniejszej pracy prezentujemy nową ogólną metodę porównywana drzew filogenetycznych. Metoda opiera się na wykorzystaniu najlżejszego doskonałego skojarzenia w grafach dwudzielnych i przy opisanych założeniach wymaga wielomianowego czasu obliczeń. W pracy omówiono podstawowe własności metryki oraz podano trzy przypadki szczególne. Przedstawiono także wyniki eksperymentów obliczeniowych.

EN

A phylogenetic tree represents historical evolutionary relationship between different species or organisms. There are various methods for reconstructing phylogenetic trees. Applying those techniques usually results in different trees for the same input data. An important problem is to determine how distant two trees reconstructed in such a way are from each other. In this paper, new metrics for comparing phylogenetics trees are suggested. These metrics are based on minimum weight perfect matching in bipartite graphs and can be computed in a polynomial time. We study same properties of these metrics and compare them with methods previously known.

Słowa kluczowe

PL

drzewo filogenetyczne; definicja metryki; czasowa złożoność obliczeniowa; wyniki eksperymentalne

EN

phylogenetic trees; metric; bipartite graphs

• Wydawca: Wydział Elektroniki, Telekomunikacji i Informatyki Politechniki Gdańskiej
• Czasopismo: Zeszyty Naukowe Wydziału ETI Politechniki Gdańskiej. Technologie Informacyjne
• Rocznik: 2008
• Tom: T. 15
• Strony: 183--188
• Opis fizyczny: Bibliogr. 10 poz, rys., tab.

Twórcy

autor

Bogdanowicz D.

• Politechnika Gdańska, Katedra Algorytmów i Modelowania Systemów, Gdańsk ul. Narutowicza 11/12

Bibliografia

• [1] Allen B. L, Steel M.: Subtree Transfer Operations and Their Induced Metrics on Evolutionary Trees, Annals of Combinatorics, nr 5, s. 1-15, 2001.
• [2] Bryant D.: The Splits in the Neighborhood of a Tree, Annals of Combinatorics, nr 8, 2004.
• [3] Robinson D. F., Foulds, L R.: Comparison of phylogenetic trees, Mathematical Biosciences nr 53, s. 131-147, 1981.
• [4] Bluis J., Shin D.-G.: Nodal Distance Algorithm: Calculating a Phylogenetic Tree Comparison Metric. W: Proceedings of the 3rd IEEE Symposium on BioInformatics and BioEngineering, 2003.
• [5] Bryant D., Tsang J., Kearney P., Li M.: Computing the quartet distance between evolutionary trees. W: Proceedings of the eleventh annual ACM-SIAM symposium on Discrete algorithms, s. 285-286, 2000.
• [6] Bryant D.: Building Trees, Hunting for Trees, and Comparing Trees - Theory and Methods in Phylogenetic Analysis, rozprawa doktorska, Department of Mathematics. University of Canterbury, 1997.
• [7] Kuhn H. W.: The Hungarian method for the assignment problem. Naval Research Logistics Quarterly, nr 2, s. 83-97, 1955.
• [8] Johnson D. S., McGeoch C.: Network Flows and Matching: First DIMACS Implementation Challenge, American Mathematical Society, 1993.
• [9] Nye T. M.W., Liò P., Gilks W. R.: A novel algorithm and web-based tool for comparing two alternative phylogenetic trees, Bioinformatics, nr 22, s. 117-119, 2006.
• [10] Yang Z.: PAML 4: a program package for phylogenetic analysis by maximum likelihood, Molecular Biology and Evolution, nr 24, s. 1586-1591, 2007.