Narzędzia help

Preferencje help
Widoczny [Schowaj] Abstrakt
Liczba wyników
first previous next last
cannonical link button

http://yadda.icm.edu.pl:80/baztech/element/bwmeta1.element.baztech-article-BPG5-0031-0057

Czasopismo

Zeszyty Naukowe Wydziału ETI Politechniki Gdańskiej. Technologie Informacyjne

Tytuł artykułu

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

Autorzy Bogdanowicz, D. 
Treść / Zawartość
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 drzewa 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.
Kolekcja BazTech
Identyfikator YADDA bwmeta1.element.baztech-article-BPG5-0031-0057
Identyfikatory