Cargando…
Comparative genomics meets topology: a novel view on genome median and halving problems
BACKGROUND: Genome median and genome halving are combinatorial optimization problems that aim at reconstruction of ancestral genomes by minimizing the number of evolutionary events between them and genomes of the extant species. While these problems have been widely studied in past decades, their so...
Autores principales: | , , |
---|---|
Formato: | Online Artículo Texto |
Lenguaje: | English |
Publicado: |
BioMed Central
2016
|
Materias: | |
Acceso en línea: | https://www.ncbi.nlm.nih.gov/pmc/articles/PMC5123253/ https://www.ncbi.nlm.nih.gov/pubmed/28185564 http://dx.doi.org/10.1186/s12859-016-1263-7 |
_version_ | 1782469695740313600 |
---|---|
author | Alexeev, Nikita Avdeyev, Pavel Alekseyev, Max A. |
author_facet | Alexeev, Nikita Avdeyev, Pavel Alekseyev, Max A. |
author_sort | Alexeev, Nikita |
collection | PubMed |
description | BACKGROUND: Genome median and genome halving are combinatorial optimization problems that aim at reconstruction of ancestral genomes by minimizing the number of evolutionary events between them and genomes of the extant species. While these problems have been widely studied in past decades, their solutions are often either not efficient or not biologically adequate. These shortcomings have been recently addressed by restricting the problems solution space. RESULTS: We show that the restricted variants of genome median and halving problems are, in fact, closely related. We demonstrate that these problems have a neat topological interpretation in terms of embedded graphs and polygon gluings. We illustrate how such interpretation can lead to solutions to these problems in particular cases. CONCLUSIONS: This study provides an unexpected link between comparative genomics and topology, and demonstrates advantages of solving genome median and halving problems within the topological framework. |
format | Online Article Text |
id | pubmed-5123253 |
institution | National Center for Biotechnology Information |
language | English |
publishDate | 2016 |
publisher | BioMed Central |
record_format | MEDLINE/PubMed |
spelling | pubmed-51232532016-12-06 Comparative genomics meets topology: a novel view on genome median and halving problems Alexeev, Nikita Avdeyev, Pavel Alekseyev, Max A. BMC Bioinformatics Research BACKGROUND: Genome median and genome halving are combinatorial optimization problems that aim at reconstruction of ancestral genomes by minimizing the number of evolutionary events between them and genomes of the extant species. While these problems have been widely studied in past decades, their solutions are often either not efficient or not biologically adequate. These shortcomings have been recently addressed by restricting the problems solution space. RESULTS: We show that the restricted variants of genome median and halving problems are, in fact, closely related. We demonstrate that these problems have a neat topological interpretation in terms of embedded graphs and polygon gluings. We illustrate how such interpretation can lead to solutions to these problems in particular cases. CONCLUSIONS: This study provides an unexpected link between comparative genomics and topology, and demonstrates advantages of solving genome median and halving problems within the topological framework. BioMed Central 2016-11-11 /pmc/articles/PMC5123253/ /pubmed/28185564 http://dx.doi.org/10.1186/s12859-016-1263-7 Text en © The Author(s) 2016 Open Access This article is distributed under the terms of the Creative Commons Attribution 4.0 International License (http://creativecommons.org/licenses/by/4.0/), which permits unrestricted use, distribution, and reproduction in any medium, provided you give appropriate credit to the original author(s) and the source, provide a link to the Creative Commons license, and indicate if changes were made. The Creative Commons Public Domain Dedication waiver(http://creativecommons.org/publicdomain/zero/1.0/) applies to the data made available in this article, unless otherwise stated. |
spellingShingle | Research Alexeev, Nikita Avdeyev, Pavel Alekseyev, Max A. Comparative genomics meets topology: a novel view on genome median and halving problems |
title | Comparative genomics meets topology: a novel view on genome median and halving problems |
title_full | Comparative genomics meets topology: a novel view on genome median and halving problems |
title_fullStr | Comparative genomics meets topology: a novel view on genome median and halving problems |
title_full_unstemmed | Comparative genomics meets topology: a novel view on genome median and halving problems |
title_short | Comparative genomics meets topology: a novel view on genome median and halving problems |
title_sort | comparative genomics meets topology: a novel view on genome median and halving problems |
topic | Research |
url | https://www.ncbi.nlm.nih.gov/pmc/articles/PMC5123253/ https://www.ncbi.nlm.nih.gov/pubmed/28185564 http://dx.doi.org/10.1186/s12859-016-1263-7 |
work_keys_str_mv | AT alexeevnikita comparativegenomicsmeetstopologyanovelviewongenomemedianandhalvingproblems AT avdeyevpavel comparativegenomicsmeetstopologyanovelviewongenomemedianandhalvingproblems AT alekseyevmaxa comparativegenomicsmeetstopologyanovelviewongenomemedianandhalvingproblems |