Thesis (Ph.D.)--University of Illinois at Urbana-Champaign, 2007. / Source: Dissertation Abstracts International, Volume: 68-11, Section: B, page: 7046. Adviser: Gustavo Caetano-Anolles. Includes bibliographical references (leaves 117-129) Available on microfilm from Pro Quest Information and Learning.

Thesis (Ph.D.)--University of California, San Francisco, 2008. / Source: Dissertation Abstracts International, Volume: 69-09, Section: B, page: 5131. Advisers: Patricia C. Babbitt; Andrej Sali.

Thesis (Ph.D.)--University of California, San Francisco, 2008. / Source: Dissertation Abstracts International, Volume: 69-09, Section: B, page: 5132. Adviser: Andrej Sali.

Thesis (Ph.D.)--University of California, San Francisco, 2008. / Source: Dissertation Abstracts International, Volume: 69-12, Section: B, page: 7232. Adviser: Hao Li.

Thesis (Ph.D.)--University of Illinois at Urbana-Champaign, 2008. / Source: Dissertation Abstracts International, Volume: 69-11, Section: B, page: 6499. Adviser: Jonathan V. Sweedler. Includes bibliographical references. Available on microfilm from Pro Quest Information and Learning.

Thesis (Ph.D.)--Indiana University, School of Informatics and Computing, 2009. / Title from PDF t.p. (viewed on Jul 22, 2010). Source: Dissertation Abstracts International, Volume: 70-12, Section: B, page: 7299. Adviser: Haixu Tang.

Thesis (M.S.)--University of California, San Francisco, 2009. / Source: Masters Abstracts International, Volume: 48-02, page: 0876. Adviser: Andrej Sali.

The Hannenhalli-Pevzner algorithm for computing the evolutionary distance between two genomes is very efficient when the genomes are signed and totally ordered. But in real comparative maps, the data suffer from problems such as coarseness, missing data, no signs, paralogy, order conflicts and mapping noise. In this thesis we have developed a suite of algorithms for genome rearrangement analysis in the presence of noise and incomplete information. For coarseness and missing data, we represent each chromosome as a partial order, summarized by a directed acyclic graph (DAG). We augment each DAG to a directed graph (DG) in which all possible linearizations are embedded. The chromosomal DGs representing two genomes are combined to produce a single bicoloured graph. The major contribution of the thesis is an algorithm for extracting a maximal decomposition of some subgraph into alternating coloured cycles, determining an optimal sequence of rearrangements, and hence the genomic distance. Also based on this framework, we have proposed an algorithm to solve all the above problems of comparative maps simultaneously by adding heuristic preprocessing to the exact algorithm approach. We have applied this to the comparison of maize and sorghum genomic maps on the GRAMENE database. A further contribution treats the inflation of genome distance by high levels of noise due to incorrectly resolved paralogy and error at the mapping, sequencing and alignment levels. We have developed an algorithm to remove the noise by maximizing strips and tested its robustness as noise levels increase.

The basic rearrangement phylogeny methods require that the genomic content be the same in all the organisms being compared, and so are not applicable when one or more of the genomes being compared derive from ancestral whole genome doubling (WGD) events. In this thesis I developed algorithms for rearrangement phylogeny for sets of related genomes that include both descendants of WGD and unduplicated genomes. Furthermore I investigated the properties of these algorithms and validated them by applying them to real data. I defined varions possible local configurations of doubled and unduplicated genomes in a given phylogeny, each of which requires a different strategy for integrating genomic distance, halving and rearrangement median algorithms. The genome halving algorithm of El-Mabrouk and Sankoff efficiently reconstructs an ancestral pre-doubling genome from the chromosomal distribution of duplicate genes created by this event and remaining today in the descendant genome. However, this algorithm can produce many alternate optimal solutions. To reduce this non-uniqeness, hopefully to only one solution, I developed the guided genome halving algorithm. This rapidly and accurately constructs an optimal ancestor closest to one or more outgroups. As I refined this algorithm, I applied it to successively larger data sets, increasing in size over more than two orders of magnitude. Thus I constructed the ancestors of cereals, based on duplicate markers in maize and using rice and sorghum as outliers. I reconstructed genomes corresponding to the ancestral nodes of yeasts in the Saccharomyces complex, as well as the ancestor of poplar, based on grapevine and papaya as outgroups. I studied two cases involving two WGD descendants, one where the doubling precedes a speciation event and another where doubling occurs independently in both lineages initiated by a speciation event. I developed combinatorial algorithms permitting us to decide which of these options best explains the data. To take into account the massive loss of genes following ancestral genome doubling, I developed a method to incorporate the defective gene sets into consideration and evaluate the effects of these lost genes on the reconstruction of the ancestor.

No description available.