Wyniki wyszukiwania - BazTech

Ograniczanie wyników

Znaleziono wyników: 1

Liczba wyników na stronie

Wyniki wyszukiwania

Wyszukiwano:
w słowach kluczowych: czasowa złożoność obliczeniowa

Sortuj według:

Ogranicz wyniki do:

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

Bogdanowicz D.

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

2008

T. 15

183-188

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.

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.