Cargando…

Ancestral Genome Inference Using a Genetic Algorithm Approach

Recent advancement of technologies has now made it routine to obtain and compare gene orders within genomes. Rearrangements of gene orders by operations such as reversal and transposition are rare events that enable researchers to reconstruct deep evolutionary histories. An important application of...

Descripción completa

Detalles Bibliográficos
Autores principales: Gao, Nan, Yang, Ning, Tang, Jijun
Formato: Online Artículo Texto
Lenguaje:English
Publicado: Public Library of Science 2013
Materias:
Acceso en línea:https://www.ncbi.nlm.nih.gov/pmc/articles/PMC3642123/
https://www.ncbi.nlm.nih.gov/pubmed/23658708
http://dx.doi.org/10.1371/journal.pone.0062156
_version_ 1782268104917647360
author Gao, Nan
Yang, Ning
Tang, Jijun
author_facet Gao, Nan
Yang, Ning
Tang, Jijun
author_sort Gao, Nan
collection PubMed
description Recent advancement of technologies has now made it routine to obtain and compare gene orders within genomes. Rearrangements of gene orders by operations such as reversal and transposition are rare events that enable researchers to reconstruct deep evolutionary histories. An important application of genome rearrangement analysis is to infer gene orders of ancestral genomes, which is valuable for identifying patterns of evolution and for modeling the evolutionary processes. Among various available methods, parsimony-based methods (including GRAPPA and MGR) are the most widely used. Since the core algorithms of these methods are solvers for the so called median problem, providing efficient and accurate median solver has attracted lots of attention in this field. The “double-cut-and-join” (DCJ) model uses the single DCJ operation to account for all genome rearrangement events. Because mathematically it is much simpler than handling events directly, parsimony methods using DCJ median solvers has better speed and accuracy. However, the DCJ median problem is NP-hard and although several exact algorithms are available, they all have great difficulties when given genomes are distant. In this paper, we present a new algorithm that combines genetic algorithm (GA) with genomic sorting to produce a new method which can solve the DCJ median problem in limited time and space, especially in large and distant datasets. Our experimental results show that this new GA-based method can find optimal or near optimal results for problems ranging from easy to very difficult. Compared to existing parsimony methods which may severely underestimate the true number of evolutionary events, the sorting-based approach can infer ancestral genomes which are much closer to their true ancestors. The code is available at http://phylo.cse.sc.edu.
format Online
Article
Text
id pubmed-3642123
institution National Center for Biotechnology Information
language English
publishDate 2013
publisher Public Library of Science
record_format MEDLINE/PubMed
spelling pubmed-36421232013-05-08 Ancestral Genome Inference Using a Genetic Algorithm Approach Gao, Nan Yang, Ning Tang, Jijun PLoS One Research Article Recent advancement of technologies has now made it routine to obtain and compare gene orders within genomes. Rearrangements of gene orders by operations such as reversal and transposition are rare events that enable researchers to reconstruct deep evolutionary histories. An important application of genome rearrangement analysis is to infer gene orders of ancestral genomes, which is valuable for identifying patterns of evolution and for modeling the evolutionary processes. Among various available methods, parsimony-based methods (including GRAPPA and MGR) are the most widely used. Since the core algorithms of these methods are solvers for the so called median problem, providing efficient and accurate median solver has attracted lots of attention in this field. The “double-cut-and-join” (DCJ) model uses the single DCJ operation to account for all genome rearrangement events. Because mathematically it is much simpler than handling events directly, parsimony methods using DCJ median solvers has better speed and accuracy. However, the DCJ median problem is NP-hard and although several exact algorithms are available, they all have great difficulties when given genomes are distant. In this paper, we present a new algorithm that combines genetic algorithm (GA) with genomic sorting to produce a new method which can solve the DCJ median problem in limited time and space, especially in large and distant datasets. Our experimental results show that this new GA-based method can find optimal or near optimal results for problems ranging from easy to very difficult. Compared to existing parsimony methods which may severely underestimate the true number of evolutionary events, the sorting-based approach can infer ancestral genomes which are much closer to their true ancestors. The code is available at http://phylo.cse.sc.edu. Public Library of Science 2013-05-02 /pmc/articles/PMC3642123/ /pubmed/23658708 http://dx.doi.org/10.1371/journal.pone.0062156 Text en © 2013 Gao et al http://creativecommons.org/licenses/by/4.0/ This is an open-access article distributed under the terms of the Creative Commons Attribution License, which permits unrestricted use, distribution, and reproduction in any medium, provided the original author and source are properly credited.
spellingShingle Research Article
Gao, Nan
Yang, Ning
Tang, Jijun
Ancestral Genome Inference Using a Genetic Algorithm Approach
title Ancestral Genome Inference Using a Genetic Algorithm Approach
title_full Ancestral Genome Inference Using a Genetic Algorithm Approach
title_fullStr Ancestral Genome Inference Using a Genetic Algorithm Approach
title_full_unstemmed Ancestral Genome Inference Using a Genetic Algorithm Approach
title_short Ancestral Genome Inference Using a Genetic Algorithm Approach
title_sort ancestral genome inference using a genetic algorithm approach
topic Research Article
url https://www.ncbi.nlm.nih.gov/pmc/articles/PMC3642123/
https://www.ncbi.nlm.nih.gov/pubmed/23658708
http://dx.doi.org/10.1371/journal.pone.0062156
work_keys_str_mv AT gaonan ancestralgenomeinferenceusingageneticalgorithmapproach
AT yangning ancestralgenomeinferenceusingageneticalgorithmapproach
AT tangjijun ancestralgenomeinferenceusingageneticalgorithmapproach