Inference of Credible Associations between Genes and Genomes

Hipotezę dotyczącą przebiegu ewolucji genów i gatunków można przedstawić w postaci drzew filogenetycznych, które ilustrują relacje przodek–potomek. Zdarzenia duplikacji, strat oraz horyzontalnego transferu genów (HGT) mogą prowadzić do niezgodności pomiędzy topologiami drzew genów i gatunków. Metoda uzgadniania drzew pozwala na zlokalizowanie takich zdarzeń, jednak jej ograniczenia oraz duża wrażliwość na błędy w topologiach drzew sprawia, że wiarygodność zdarzeń ewolucyjnych oraz opracowanie wiarygodnych metod rekonstruowania zdarzeń retykulacyjnych, wciąż stanowią otwarty problem w dziedzinie filogenetyki. W niniejszej rozprawie zaproponowaliśmy nowe podejście do oceny wiarygodności duplikacji i specjacji. Zdefiniowaliśmy miarę wsparcia dla tych zdarzeń i opracowaliśmy liniowy algorytm, oparty na nieukorzenionym uzgadnianiu drzew i nieparametrycznym bootstrapie, do jej obliczania. Pokazaliśmy również zastosowanie naszej metody do problemów ukorzeniania drzew i budowy superdrzew. Aby odpowiedzieć na potrzeby badań metagenomicznych i mikrobiologicznych, podjęliśmy temat lokalizowania wiarygodnych zdarzeń HGT. Zaproponowaliśmy nową miarę opartą na nieparametrycznym bootstrapie, zwaną wsparciem transferu, i wykorzystaliśmy ją do stworzenia nowego i wydajnego algorytmu heurystycznego, który iteracyjnie znajduje acykliczne i dobrze wspierane transfery genów. Nasza metoda, oparta na kwadratowym algorytmie uzgadniania, postuluje najbardziej prawdopodobne miejsca transferów na podstawie ich wiarygodności. Innym wyzwaniem, które pojawia się w badaniach metagenomicznych, jest problem przyporządkowania genów do gatunków po wykorzystaniu metody sekwencjonowania typu shotgun, w której te przyporządkowania mogą zostać utracone. Do rekonstrukcji relacji gen–gatunek zaproponowaliśmy pierwsze tego rodzaju podejście, oparte na uzgadnianiu z transferami, umożliwiające zastosowanie dwóch modeli: spójnego czasowo (tcDTL) i ogólnego (DTL). Algorytm dla modelu DTL działa w czasie kwadratowym, natomiast dla modelu tcDTL opisujemy rozwiązanie w czasie sześciennym z kilkoma ulepszeniami i uogólnieniami. Na końcu, skupiliśmy się na przypadku, gdy drzewa filogenetyczne są niewystarczające do przedstawienia złożonych relacji ewolucyjnych. Nasze podejście oparte na sieciach zastosowaliśmy do zbiorów danych zawierających sekwencje, których duże podobieństwo uniemożliwia zbudowanie wiarygodnych drzew filogenetycznych. Sieci otrzymane dla sekwencji receptora BCR, pochodzących z limfocytów B pobranych od pacjentów z chłoniakiem pęcherzykowym, pozwalają modelować ewolucję nowotworu i obserwować selekcję subklonalną indukowaną przez mutacje BCR.

Hypothesis of the course of gene and species evolution can be represented as a phylogenetic tree, which illustrates the ancestor–descendant relationships. Events such as gene duplications, losses and horizontal gene transfers (HGT) can lead to the incongruence of the gene and its species tree. To locate such events, one can use tree reconciliation. However, this method is prone to topology errors, therefore, assessing the credibility of evolutionary events and reliable inference of reticulate evolution are important issues in phylogenetics. In this dissertation we propose a novel approach to assess credibility of gene duplications and speciations. We developed a linear time algorithm, based on unrooted reconciliation and non-parametric bootstrap, which calculates support values for evolutionary events. We also show the application of our method to the rooting and supertree problems. To address the needs of metagenomic and microbial studies, we investigated the problem of the inference of well-supported HGT events. We propose a new measure based on non-parametric bootstrap, called transfer support. Then, we use it to design a new, efficient heuristic algorithm that iteratively infers acyclic and well-supported transfer scenarios. Our method, based on a novel square time HGT-reconciliation algorithm, postulates the most probable locations based on the extended tree reconciliation and credibility of inferred HGTs. Another challenge in metagenomic studies is the gene-species assignment problem, i.e., the problem of mapping of genes of unknown origin to a particular species after shotgun sequencing. To address the problem, we propose the first HGT-reconciliation based approach to infer such mappings with two tractable HGT-models: time consistent (tcDTL) and general (DTL). The algorithm for the DTL model runs in square time, while for the tcDTL model, we describe a cubic time solution with several improvements and generalizations. Finally, we propose a novel network-based approach to datasets containing sequences whose high similarity prevents a credible phylogenetic tree inference. We apply the methods to BCR receptor sequences from B-cells of follicular lymphoma patients, which allowed us to model tumor evolution and observe subclonal selec tion driven by BCR mutations.