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...

Descripción completa

Detalles Bibliográficos
Autores principales: Alexeev, Nikita, Avdeyev, Pavel, Alekseyev, Max A.
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