Cargando…
Genomic distance under gene substitutions
BACKGROUND: The distance between two genomes is often computed by comparing only the common markers between them. Some approaches are also able to deal with non-common markers, allowing the insertion or the deletion of such markers. In these models, a deletion and a subsequent insertion that occur a...
Autores principales: | , , , |
---|---|
Formato: | Online Artículo Texto |
Lenguaje: | English |
Publicado: |
BioMed Central
2011
|
Materias: | |
Acceso en línea: | https://www.ncbi.nlm.nih.gov/pmc/articles/PMC3271670/ https://www.ncbi.nlm.nih.gov/pubmed/22151231 http://dx.doi.org/10.1186/1471-2105-12-S9-S8 |
_version_ | 1782222745010962432 |
---|---|
author | Braga, Marília D V Machado, Raphael Ribeiro, Leonardo C Stoye, Jens |
author_facet | Braga, Marília D V Machado, Raphael Ribeiro, Leonardo C Stoye, Jens |
author_sort | Braga, Marília D V |
collection | PubMed |
description | BACKGROUND: The distance between two genomes is often computed by comparing only the common markers between them. Some approaches are also able to deal with non-common markers, allowing the insertion or the deletion of such markers. In these models, a deletion and a subsequent insertion that occur at the same position of the genome count for two sorting steps. RESULTS: Here we propose a new model that sorts non-common markers with substitutions, which are more powerful operations that comprehend insertions and deletions. A deletion and an insertion that occur at the same position of the genome can be modeled as a substitution, counting for a single sorting step. CONCLUSIONS: Comparing genomes with unequal content, but without duplicated markers, we give a linear time algorithm to compute the genomic distance considering substitutions and double-cut-and-join (DCJ) operations. This model provides a parsimonious genomic distance to handle genomes free of duplicated markers, that is in practice a lower bound to the real genomic distances. The method could also be used to refine orthology assignments, since in some cases a substitution could actually correspond to an unannotated orthology. |
format | Online Article Text |
id | pubmed-3271670 |
institution | National Center for Biotechnology Information |
language | English |
publishDate | 2011 |
publisher | BioMed Central |
record_format | MEDLINE/PubMed |
spelling | pubmed-32716702012-02-04 Genomic distance under gene substitutions Braga, Marília D V Machado, Raphael Ribeiro, Leonardo C Stoye, Jens BMC Bioinformatics Proceedings BACKGROUND: The distance between two genomes is often computed by comparing only the common markers between them. Some approaches are also able to deal with non-common markers, allowing the insertion or the deletion of such markers. In these models, a deletion and a subsequent insertion that occur at the same position of the genome count for two sorting steps. RESULTS: Here we propose a new model that sorts non-common markers with substitutions, which are more powerful operations that comprehend insertions and deletions. A deletion and an insertion that occur at the same position of the genome can be modeled as a substitution, counting for a single sorting step. CONCLUSIONS: Comparing genomes with unequal content, but without duplicated markers, we give a linear time algorithm to compute the genomic distance considering substitutions and double-cut-and-join (DCJ) operations. This model provides a parsimonious genomic distance to handle genomes free of duplicated markers, that is in practice a lower bound to the real genomic distances. The method could also be used to refine orthology assignments, since in some cases a substitution could actually correspond to an unannotated orthology. BioMed Central 2011-10-05 /pmc/articles/PMC3271670/ /pubmed/22151231 http://dx.doi.org/10.1186/1471-2105-12-S9-S8 Text en Copyright ©2011 Braga et al; 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 | Proceedings Braga, Marília D V Machado, Raphael Ribeiro, Leonardo C Stoye, Jens Genomic distance under gene substitutions |
title | Genomic distance under gene substitutions |
title_full | Genomic distance under gene substitutions |
title_fullStr | Genomic distance under gene substitutions |
title_full_unstemmed | Genomic distance under gene substitutions |
title_short | Genomic distance under gene substitutions |
title_sort | genomic distance under gene substitutions |
topic | Proceedings |
url | https://www.ncbi.nlm.nih.gov/pmc/articles/PMC3271670/ https://www.ncbi.nlm.nih.gov/pubmed/22151231 http://dx.doi.org/10.1186/1471-2105-12-S9-S8 |
work_keys_str_mv | AT bragamariliadv genomicdistanceundergenesubstitutions AT machadoraphael genomicdistanceundergenesubstitutions AT ribeiroleonardoc genomicdistanceundergenesubstitutions AT stoyejens genomicdistanceundergenesubstitutions |