Spelling suggestions: "subject:"checkpoint graph""
1 |
Escape from Parsimony of Different Models of Genome Evolution ProcessesMeghdari Miardan, Mona 09 March 2022 (has links)
In the course of evolution, genomes diverge from their ancestors either via global mutations and by rearrangement of their chromosomal segments, or through local mutations within their genes. In this thesis (Chapters: 2, 3 and 4) we analyze the evolution of genomes based on different rearrangement operations including: in Chapter 2 both restricted and unrestricted double-cut-and-join (DCJ) operations, in Chapter 3 both internal and general reversal and translocation (IRT and HP, respectively) operations, and in Chapter 4 translocation, weighted reversal (WR) and maximum length reversal (MLR) operations. Based on the rearrangement operation chosen we can model the evolution of genomes as a discrete or continuous-time Markov chain process on the space of signed genomes.
For each model of evolution, we study the stochastic process by investigating the time up to which the difference between the number of operations along the evolutionary trajectory and the edit distance of the genome from its ancestor is negligible, as soon as these two values starts diverging drastically from one another we say the process escapes from parsimony. One of the major parameters in the known edit distance formulas between any two genomes (such as reversal, DCJ, IRT, HP and translocation) is the number of cycles in their breakpoint graph.
For DCJ, IRT and HP models by adopting the method elaborated by Berestycki and Durret, we estimate the number of cycles in the breakpoint graph of the genome at time t and its ancestor by the number of tree components of the random graph constructed from the model of evolution at time t, which is an Erdös-Rényi. We also proved that for each of the DCJ, IRT and HP models of evolution, the process on a genome of size n is bound to its parsimonious estimate up to t ≈ n/2 steps.
Since the random graph constructed from the models of evolution for the translocation, WR and MLR processes are not Erdös-Rényi, the proofs of their parsimony- bound require more advanced mathematical tools, however our simulation shows for the translocation, two types of WR, and MLR (except for reversals with very short maximum length) models, the escape from parsimony do not occur before n/2 steps, where n is the number of genes in the genome.
A basic result in this field is due to Berestycki and Durrett, from 2006, who found that a random transposition (pairwise exchange of the elements in the corresponding permutation of the genome) evolves along its parsimonious path of evolution up to n/2 steps, where n is the number of the genes. Although, this transposition model is applicable solely for evolution of a unichromosomal ancestor which remains unichromosomal at each step t of the process; however for the DCJ, IRT, HP and translocation models the genomes are multichromosomal which increases the difficulty of the problem at hand.
The models studied in Chapters 2 - 4 are all based on signed permutation representations of genomes, where each "gene" occurs exactly once, with either positive or negative polarity. The same genes occur in all the genomes being considered. There is no distinction between the same gene in two different genomes. In Chapter 5 we generalize our representation to genes that may have several copies of a gene, which differ only by a few point mutations. This leads to problems of identifying copies in two genomes that are primary orthologs, under the assumptions of differentials in point mutation rate. We provide algorithms, software and test examples.
|
Page generated in 0.0504 seconds