Inferring genomic duplication events

Jednym z fundamentalnych zagadnień w molekularnej biologii obliczeniowej jest wykrywanie zdarzeń duplikacji w genomie oraz określenie ich położenia w drzewie gatunków. Rekonstrukcja tych zdarzeń jest możliwa poprzez klastrowanie pojedynczych duplikacji genu, wyznaczonych przez uzgadnianie zbioru drzew genów ze zbiorem gatunków. Istniejące metody różnią się w dwóch zasadniczych kwestiach: (a) wyboru scenariuszy ewolucyjnych, które modelują dopuszczalne lokalizacje duplikacji w drzewie gatunków oraz (b) określenia zasad klastrowania duplikacji genów z drzew genów w jedno zdarzenie wielokrotnej duplikacji, metod jak np. episode clustering (EC) lub minimum episodes (ME). Analizując literaturę można wyróżnić kilka modeli opisujących jak duplikacje genów z drzew rodzin genów interpretować jako jedno zdarzenie, jednak wszystkie one dotyczą przypadku, gdy drzewa genów są ukorzenione. Warunek ten ogranicza możliwości zastosowań, gdyż to nieukorzenione drzewa genów są wynikiem popularnych metod filogenetycznych.W niniejszej rozprawie, proponujemy model scenariuszy ewolucyjnych, który zachowuje minimalną liczbę duplikacji genów. Badamy problem RME, czyli klastrowania metodą ME w przypadku, gdy wejściowe drzewa genów są ukorzenione. Przeanalizowaliśmy kilka modeli dopuszczalnych scenariuszy ewolucyjnych, ze szczególnym uwzględnieniem modeli interwałowych, w których każda duplikacja genu ma przypisany interwał dopuszczalnych lokalizacji w drzewie gatunków, oraz nakładających dodatkowe ograniczenia jak monotoniczność. Przedstawiamy matematyczne podstawy dla ogólnych problemów duplikacji genomowych. Następnie, dla problemu RME proponujemy pierwszy liniowy algorytm uniwersalny dla modeli interwałowych oraz algorytm dla najbardziej ogólnego modelu, w którym każdy scenariusz ewolucyjny jest dopuszczalny. Dodatkowo przedstawiamy studium porównawcze dla różnych modeli duplikacji genomowych, które bazuje na danych symulowanych i empirycznych. Dostarczamy algorytmów i narzędzi do efektywnego rozwiązywania problemów RME dla różnych modeli. Nasze studium porównawcze pozwala na zidentyfikowanie, który model stanowi najrozsądniejszy wybór przy wnioskowaniu zdarzeń duplikacji genomu.Niniejsza rozprawa przedstawia pierwsze rozwiązania dla otwartych problemów UEC (episode clustering) i UME (minimum episodes), w których każdy scenariusz implikujący minimalną liczbę pojedynczych duplikacji genu jest dopuszczalny oraz przyjmujemy założenie, że wejściowe drzewa genów są nieukorzenione. W szczególności prezentujemy nowe teoretyczne własności nieukorzenionego uzgadniania dla kosztu duplikacyjnego i wykorzystujemy je do zaprojektowania dokładnych i heurystycznych algorytmów rozwiązujących problemy duplikacji genomowych. Nasza ewaluacja eksperymentalna pokazuje, że potrafimy ulepszyć znane wyniki dla wnioskowania duplikacji genomowych z ukorzenionych drzew. Dodatkowo nasza analiza na empirycznych danych potwierdziła kilka zdarzeń duplikacji genomowych z literatury demonstrując, że proponowane algorytmy można z sukcesem wykorzystywać w praktyce.

One of evolutionary molecular biology fundamental problems is to discover genomic duplication events and their locations in the species tree. Such events can be reconstructed by clustering single gene duplications inferred by reconciling a set of gene trees with a species tree. Existing reconciliation based approaches vary in the two fundamental aspects: (a) the choice of evolutionary scenarios that model allowed locations of duplications in the species tree, and (b) the rules of clustering gene duplications from gene trees into a single multiple duplication event, i.e., episode clustering (EC) or minimum episodes (ME) methods. There are several models in the literature that specify how gene duplications from gene families can be interpreted as one duplication episode. However, in all duplication episode problems gene trees are rooted. This restriction limits the applicability, since unrooted gene family trees are frequently inferred by phylogenetic methods.In this dissertation, we propose a model of evolutionary scenarios that preserves the minimal number of gene duplications. We study the RME problem, that is, ME method of clustering when input gene trees are rooted. Our analysis concerns several models of allowed evolutionary scenarios with a focus on interval models in which every gene duplication has an interval consisting of allowed locations in the species tree and fulfills some additional requirements like monotonicity. We present mathematical foundations for general genomic duplication problems. Next, we propose the first linear time and space algorithm for RME jointly for any interval model and the algorithm for the most general model in which every evolutionary scenario is allowed. We also present a comparative study of different models of genomic duplication based on simulated and empirical datasets. We provide algorithms and tools that can be applied to solve RME problems efficiently for various models. Our comparative study helps to identify which model is the most reasonable choice in inferring genomic duplication events.This dissertation proposes the first solutions to the open problems of UEC (unrooted episode clustering) and UME (unrooted minimum episodes) in which every reconciliation with the minimal number of single gene duplications is allowed and under the assumption that input gene trees are unrooted. In particular, we show new theoretical properties of unrooted reconciliation for the duplication cost and apply them to design several exact and heuristic algorithms for solving the genomic duplication problems. Our comparative study shows that we can improve known results on genomic duplication inference from rooted trees. Moreover, our evaluation on empirical datasets confirms several genomic duplication events from the literature and demonstrates that the proposed algorithms can be successfully applied in practice.