Guided genome halving: hardness, heuristics and the history of the Hemiascomycetes
Authors:
Open Access
- 1 July 2008
- journal article
- research article
- Published by Oxford University Press (OUP) in Bioinformatics
- Vol. 24 (13) , i96-i104
Abstract
Motivation: Some present day species have incurred a whole genome doubling event in their evolutionary history, and this is reflected today in patterns of duplicated segments scattered throughout their chromosomes. These duplications may be used as data to ‘halve’ the genome, i.e. to reconstruct the ancestral genome at the moment of doubling, but the solution is often highly nonunique. To resolve this problem, we take account of outgroups, external reference genomes, to guide and narrow down the search. Results: We improve on a previous, computationally costly, ‘brute force’ method by adapting the genome halving algorithm of El-Mabrouk and Sankoff so that it rapidly and accurately constructs an ancestor close the outgroups, prior to a local optimization heuristic. We apply this to reconstruct the predoubling ancestor of Saccharomyces cerevisiae and Candida glabrata, guided by the genomes of three other yeasts that diverged before the genome doubling event. We analyze the results in terms (1) of the minimum evolution criterion, (2) how close the genome halving result is to the final (local) minimum and (3) how close the final result is to an ancestor manually constructed by an expert with access to additional information. We also visualize the set of reconstructed ancestors using classic multidimensional scaling to see what aspects of the two doubled and three unduplicated genomes influence the differences among the reconstructions. Availability: The experimental software is available on request. Contact: sankoff@uottawa.caKeywords
This publication has 17 references indexed in Scilit:
- Polyploids, genome halving and phylogenyBioinformatics, 2007
- A Unifying View of Genome Rearrangements2006
- The Yeast Gene Order Browser: Combining curated homology and syntenic context reveals gene fate in polyploid speciesGenome Research, 2005
- Efficient sorting of genomic permutations by translocation, inversion and block interchangeBioinformatics, 2005
- Genome evolution in yeastsNature, 2004
- Phylogenetic relationships among yeasts of the ? complex? determined from multigene sequence analysesFEMS Yeast Research, 2003
- The Reversal Median ProblemINFORMS Journal on Computing, 2003
- The Reconstruction of Doubled GenomesSIAM Journal on Computing, 2003
- Efficient algorithms for multichromosomal genome rearrangementsJournal of Computer and System Sciences, 2002
- Some distance properties of latent root and vector methods used in multivariate analysisBiometrika, 1966