Cargando…

Genome aliquoting with double cut and join

BACKGROUND: The genome aliquoting probem is, given an observed genome A with n copies of each gene, presumed to descend from an n-way polyploidization event from an ordinary diploid genome B, followed by a history of chromosomal rearrangements, to reconstruct the identity of the original genome B�...

Descripción completa

Detalles Bibliográficos
Autores principales: Warren, Robert, Sankoff, David
Formato: Texto
Lenguaje:English
Publicado: BioMed Central 2009
Materias:
Acceso en línea:https://www.ncbi.nlm.nih.gov/pmc/articles/PMC2648758/
https://www.ncbi.nlm.nih.gov/pubmed/19208119
http://dx.doi.org/10.1186/1471-2105-10-S1-S2
_version_ 1782164981312126976
author Warren, Robert
Sankoff, David
author_facet Warren, Robert
Sankoff, David
author_sort Warren, Robert
collection PubMed
description BACKGROUND: The genome aliquoting probem is, given an observed genome A with n copies of each gene, presumed to descend from an n-way polyploidization event from an ordinary diploid genome B, followed by a history of chromosomal rearrangements, to reconstruct the identity of the original genome B'. The idea is to construct B', containing exactly one copy of each gene, so as to minimize the number of rearrangements d(A, B' ⊕ B' ⊕ ... ⊕ B') necessary to convert the observed genome B' ⊕ B' ⊕ ... ⊕ B' into A. RESULTS: In this paper we make the first attempt to define and solve the genome aliquoting problem. We present a heuristic algorithm for the problem as well the data from our experiments demonstrating its validity. CONCLUSION: The heuristic performs well, consistently giving a non-trivial result. The question as to the existence or non-existence of an exact solution to this problem remains open.
format Text
id pubmed-2648758
institution National Center for Biotechnology Information
language English
publishDate 2009
publisher BioMed Central
record_format MEDLINE/PubMed
spelling pubmed-26487582009-03-03 Genome aliquoting with double cut and join Warren, Robert Sankoff, David BMC Bioinformatics Research BACKGROUND: The genome aliquoting probem is, given an observed genome A with n copies of each gene, presumed to descend from an n-way polyploidization event from an ordinary diploid genome B, followed by a history of chromosomal rearrangements, to reconstruct the identity of the original genome B'. The idea is to construct B', containing exactly one copy of each gene, so as to minimize the number of rearrangements d(A, B' ⊕ B' ⊕ ... ⊕ B') necessary to convert the observed genome B' ⊕ B' ⊕ ... ⊕ B' into A. RESULTS: In this paper we make the first attempt to define and solve the genome aliquoting problem. We present a heuristic algorithm for the problem as well the data from our experiments demonstrating its validity. CONCLUSION: The heuristic performs well, consistently giving a non-trivial result. The question as to the existence or non-existence of an exact solution to this problem remains open. BioMed Central 2009-01-30 /pmc/articles/PMC2648758/ /pubmed/19208119 http://dx.doi.org/10.1186/1471-2105-10-S1-S2 Text en Copyright © 2009 Warren and Sankoff; licensee BioMed Central Ltd. http://creativecommons.org/licenses/by/2.0 This is an open access article distributed under the terms of the Creative Commons Attribution License ( (http://creativecommons.org/licenses/by/2.0) ), which permits unrestricted use, distribution, and reproduction in any medium, provided the original work is properly cited.
spellingShingle Research
Warren, Robert
Sankoff, David
Genome aliquoting with double cut and join
title Genome aliquoting with double cut and join
title_full Genome aliquoting with double cut and join
title_fullStr Genome aliquoting with double cut and join
title_full_unstemmed Genome aliquoting with double cut and join
title_short Genome aliquoting with double cut and join
title_sort genome aliquoting with double cut and join
topic Research
url https://www.ncbi.nlm.nih.gov/pmc/articles/PMC2648758/
https://www.ncbi.nlm.nih.gov/pubmed/19208119
http://dx.doi.org/10.1186/1471-2105-10-S1-S2
work_keys_str_mv AT warrenrobert genomealiquotingwithdoublecutandjoin
AT sankoffdavid genomealiquotingwithdoublecutandjoin