Segmenting Genetic Sequences Based on Common Ancestry

[摘要] In this work, I developed an algorithm that segments genetic sequences from multiple species and clusters them into groups of subsequences that are likely to be evolved from a single tree.Traditionally, the evolutionary history of a set of taxa is inferred with the assumption that the majority of genetic changes are passed on from ancestors to descendants.However, this assumption is violated when analyzing the evolution of organisms where genetic materials are often exchanged between unrelated individuals.These exchanges can result in genes with different ancestries combining and giving rise to genomes that do not fit a single tree.To better understand the evolution of these organisms, it is imperative to develop methods that delineate regions of single ancestries in the genomes and cluster subsequences into groups from which trees could be built. As of the time of writing this thesis,methods have already been developed for clustering genetic sequences based on function and for identifying gene fusion events.However, to the best of our knowledge, there are no existing techniques that cluster genetic sequences into groups based exclusively on ancestry.In this work, I designed an algorithm that generates a sequence similarity graph from a user-specified collection of genetic sequences.The algorithm then optimizes the clustering of the graph based on sequence alignment techniques, resulting in groups of sequences that are highly likely to have similar ancestries.This method was tested on simulated sequences andproduced clusters of sequences that have high probabilities of evolving from a single tree.With this method, we will be able to more accurately infer the evolution of organisms with frequent gene transfers between unrelated individuals.

[发布机构] Rice University

[效力级别] Genetic