Markov chains and applications in phylogenetics

Łańcuchy Markowa są modelami matematycznymi zjawisk zmieniających się w sposób losowy w czasie. Ich prosta struktura pozwala powiedzieć bardzo wiele na temat ich zachowania. Równocześnie są one dostatecznie skomplikowane, by znaleźć zastosowania w bardzo wielu dziedzinach nauki, m. in. w fizyce, chemii, biologii, ekonomii i finansach. Nazwa tego procesu losowego pochodzi od nazwiska rosyjskiego matematyka A. A. Markowa. Markow opublikował ponad 120 prac, przy czym około jedna trzecia dotyczyła zagadnień związanych z teorią prawdopodobieństwa. Pomysłem łańcuchów podzielił się w jednej z publikacji w 1907 roku. Zaskakujące jest to, że Markow nie przewidział szerokiego zastosowania swojej teorii. Aby wskazać użyteczność łańcuchów, przeanalizował ciąg 200000 liter z poematu Puszkina "Eugeniusz Oniegin", dowodząc, że następstwo samogłosek i spółgłosek w tym tekście jest dokładnie opisane przez pewien łańcuch Markowa z odpowiednią macierzą przejścia.Na bazie teorii łańcuchów Markowa zbudowano także bardziej skomplikowane struktury, takie jak ukryte modele Markowa. W latach 60. poprzedniego wieku zaczęto je powszechnie wykorzystywać w algorytmach rozpoznawania mowy. Z czasem zauważono, że można modelować w podobny sposób inne zjawiska obserwowane w przyrodzie. Łańcuchy Markowa znalazły szerokie zastosowanie w biologii molekularnej, a w szczególności w filogenetyce. Nauka ta zajmuje się ewolucyjnymi powiązaniami między organizmami żywymi, które przedstawia się w postaci tzw. drzew filogenetycznych. Praca składa się z dwóch części. W pierwszej opisano wybrane elementy teorii łańcuchów Markowa z czasem dyskretnym oraz rozszerzono omówione rezultaty na procesy z czasem ciągłym. Dalej zaprezentowano ukryte modele Markowa, w których obserwowane zdarzenia zależne są od nieznanych realizacji pewnego procesu Markowa. Przedstawiono definicję modelu, algorytmy prefiksowy-sufiksowy i Bauma-Welcha (służące do estymacji jego parametrów) oraz algorytm Viterbiego (pozwalający oszacować sekwencję stanów ukrytego łańcucha Markowa). Druga część pracy obejmuje zastosowanie przedstawionej wcześniej teorii w filogenetyce. Omówiono wybrane probabilistyczne modele ewolucji sekwencji DNA organizmów, będące w istocie łańcuchami Markowa z czasem ciągłym. Dalej zaprezentowano sposoby rekonstrukcji drzew filogenetycznych opartych na tych modelach ewolucji oraz przedstawiono filogenetyczne ukryte modele Markowa, stanowiące rozbudowaną wersję klasycznego drzewa filogenetycznego.

Markov chains are mathematical models for phenomena evolvind randomly in time. Their simple structure makes possible to tell a great deal about their behaviour. At the same time they are sufficiently complicated to serve in many applications, e.g. in physics, chemistry, biology, economics and finance. Markov chains are named after the Russian mathematician A. A. Markov. The idea of chains emerged in his paper of 1907. It is suprising that Markov did not foresee a wide application of his theory. To indicate the usefulness of Markov chains he analyzed the sequence of 200000 letters from a poem by Pushkin "Eugene Onegin " to show that the sequence of vowels and consonants in the text is accurately described by a Markov chain with an appropriate transition matrix.Markov chains are also widely used in molecular biology, especially in phylogenetics - the study of evolutionary relationships among organisms, which are illustrated by phylogenetic trees.This paper consists of two parts. The first one describes some of the elements of the theory of Markov chains with discrete time and discussed the results of the extended processes with continuous time. Next we presents hidden Markov models in which the observed events are dependent on the unknown realization of a Markov process.The second part of the paper involves the use of the theory presented earlier in phylogenetics. We presents some probabilistic models of evolution based on DNA sequences. Next we give methods of reconstruction of phylogenetic trees based on these models and describes phylogenetic hidden Markov models, which are extended version of the classic phylogenetic tree.