Cargando…
Guided genome halving: hardness, heuristics and the history of the Hemiascomycetes
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...
Autores principales: | , , , |
---|---|
Formato: | Texto |
Lenguaje: | English |
Publicado: |
Oxford University Press
2008
|
Materias: | |
Acceso en línea: | https://www.ncbi.nlm.nih.gov/pmc/articles/PMC2718624/ https://www.ncbi.nlm.nih.gov/pubmed/18586750 http://dx.doi.org/10.1093/bioinformatics/btn146 |
_version_ | 1782170001928617984 |
---|---|
author | Zheng, Chunfang Zhu, Qian Adam, Zaky Sankoff, David |
author_facet | Zheng, Chunfang Zhu, Qian Adam, Zaky Sankoff, David |
author_sort | Zheng, Chunfang |
collection | PubMed |
description | 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.ca |
format | Text |
id | pubmed-2718624 |
institution | National Center for Biotechnology Information |
language | English |
publishDate | 2008 |
publisher | Oxford University Press |
record_format | MEDLINE/PubMed |
spelling | pubmed-27186242009-07-31 Guided genome halving: hardness, heuristics and the history of the Hemiascomycetes Zheng, Chunfang Zhu, Qian Adam, Zaky Sankoff, David Bioinformatics Ismb 2008 Conference Proceedings 19–23 July 2008, Toronto 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.ca Oxford University Press 2008-07-01 /pmc/articles/PMC2718624/ /pubmed/18586750 http://dx.doi.org/10.1093/bioinformatics/btn146 Text en © 2008 The Author(s) http://creativecommons.org/licenses/by-nc/2.0/uk/ This is an Open Access article distributed under the terms of the Creative Commons Attribution Non-Commercial License (http://creativecommons.org/licenses/by-nc/2.0/uk/) which permits unrestricted non-commercial use, distribution, and reproduction in any medium, provided the original work is properly cited. |
spellingShingle | Ismb 2008 Conference Proceedings 19–23 July 2008, Toronto Zheng, Chunfang Zhu, Qian Adam, Zaky Sankoff, David Guided genome halving: hardness, heuristics and the history of the Hemiascomycetes |
title | Guided genome halving: hardness, heuristics and the history of the Hemiascomycetes |
title_full | Guided genome halving: hardness, heuristics and the history of the Hemiascomycetes |
title_fullStr | Guided genome halving: hardness, heuristics and the history of the Hemiascomycetes |
title_full_unstemmed | Guided genome halving: hardness, heuristics and the history of the Hemiascomycetes |
title_short | Guided genome halving: hardness, heuristics and the history of the Hemiascomycetes |
title_sort | guided genome halving: hardness, heuristics and the history of the hemiascomycetes |
topic | Ismb 2008 Conference Proceedings 19–23 July 2008, Toronto |
url | https://www.ncbi.nlm.nih.gov/pmc/articles/PMC2718624/ https://www.ncbi.nlm.nih.gov/pubmed/18586750 http://dx.doi.org/10.1093/bioinformatics/btn146 |
work_keys_str_mv | AT zhengchunfang guidedgenomehalvinghardnessheuristicsandthehistoryofthehemiascomycetes AT zhuqian guidedgenomehalvinghardnessheuristicsandthehistoryofthehemiascomycetes AT adamzaky guidedgenomehalvinghardnessheuristicsandthehistoryofthehemiascomycetes AT sankoffdavid guidedgenomehalvinghardnessheuristicsandthehistoryofthehemiascomycetes |