On the weight of indels in genomic distances

Braga MDV, Machado R, Ribeiro LC, Stoye J (2011)
BMC Bioinformatics 12(Suppl 9: RECOMB-CG 2011).

Download
OA
Journal Article | Published | English
Author
; ; ;
Abstract
Background: Classical approaches to compute the genomic distance are usually limited to genomes with the same content, without duplicated markers. However, differences in the gene content are frequently observed and can reflect important evolutionary aspects. A few polynomial time algorithms that include genome rearrangements, insertions and deletions (or substitutions) were already proposed. These methods often allow a block of contiguous markers to be inserted, deleted or substituted at once but result in distance functions that do not respect the triangular inequality and hence do not constitute metrics. Results: In the present study we discuss the disruption of the triangular inequality in some of the available methods and give a framework to establish an efficient correction for two models recently proposed, one that includes insertions, deletions and double cut and join (DCJ) operations, and one that includes substitutions and DCJ operations. Conclusions: We show that the proposed framework establishes the triangular inequality in both distances, by summing a surcharge on indel operations and on substitutions that depends only on the number of markers affected by these operations. This correction can be applied a posteriori, without interfering with the already available formulas to compute these distances. We claim that this correction leads to distances that are biologically more plausible.
Publishing Year
ISSN
PUB-ID

Cite this

Braga MDV, Machado R, Ribeiro LC, Stoye J. On the weight of indels in genomic distances. BMC Bioinformatics. 2011;12(Suppl 9: RECOMB-CG 2011).
Braga, M. D. V., Machado, R., Ribeiro, L. C., & Stoye, J. (2011). On the weight of indels in genomic distances. BMC Bioinformatics, 12(Suppl 9: RECOMB-CG 2011).
Braga, M. D. V., Machado, R., Ribeiro, L. C., and Stoye, J. (2011). On the weight of indels in genomic distances. BMC Bioinformatics 12.
Braga, M.D.V., et al., 2011. On the weight of indels in genomic distances. BMC Bioinformatics, 12(Suppl 9: RECOMB-CG 2011).
M.D.V. Braga, et al., “On the weight of indels in genomic distances”, BMC Bioinformatics, vol. 12, 2011.
Braga, M.D.V., Machado, R., Ribeiro, L.C., Stoye, J.: On the weight of indels in genomic distances. BMC Bioinformatics. 12, (2011).
Braga, Marília D. V., Machado, Raphael, Ribeiro, Leonardo C., and Stoye, Jens. “On the weight of indels in genomic distances”. BMC Bioinformatics 12.Suppl 9: RECOMB-CG 2011 (2011).
Main File(s)
Access Level
OA Open Access
Last Uploaded
2012-02-07 15:37:09

This data publication is cited in the following publications:
This publication cites the following data publications:

3 Citations in Europe PMC

Data provided by Europe PubMed Central.

DCJ-indel and DCJ-substitution distances with distinct operation costs.
da Silva PH, Machado R, Dantas S, Braga MD., Algorithms Mol Biol 8(1), 2013
PMID: 23879938
DCJ-Indel sorting revisited.
Compeau PE., Algorithms Mol Biol 8(1), 2013
PMID: 23452758
Genomic distance under gene substitutions.
Braga MD, Machado R, Ribeiro LC, Stoye J., BMC Bioinformatics 12 Suppl 9(), 2011
PMID: 22151231

12 References

Data provided by Europe PubMed Central.

Transforming men into mice (polynomial algorithm for genomic distance problem)
AUTHOR UNKNOWN, 1995
Efficient sorting of genomic permutations by translocation, inversion and block interchange.
Yancopoulos S, Attie O, Friedberg R., Bioinformatics 21(16), 2005
PMID: 15951307
A unifying view of genome rearrangements
AUTHOR UNKNOWN, 2006
The solution space of sorting by DCJ.
Braga MD, Stoye J., J. Comput. Biol. 17(9), 2010
PMID: 20874401
Genome rearrangement with gene families.
Sankoff D., Bioinformatics 15(11), 1999
PMID: 10743557
The complexity of calculating exemplar distances
AUTHOR UNKNOWN, 2000
Genomic distances under deletions and insertions
AUTHOR UNKNOWN, 2004
Genome rearrangements with duplications.
Bader M., BMC Bioinformatics 11 Suppl 1(), 2010
PMID: 20122199
Sorting Signed Permutations by Reversals and Insertions/Deletions of Contiguous Segments
AUTHOR UNKNOWN, 2001
Double cut and join with insertions and deletions.
Braga MD, Willing E, Stoye J., J. Comput. Biol. 18(9), 2011
PMID: 21899423
Genomic distance under gene substitutions.
Braga MD, Machado R, Ribeiro LC, Stoye J., BMC Bioinformatics 12 Suppl 9(), 2011
PMID: 22151231

Export

0 Marked Publications

Open Data PUB

Web of Science

View record in Web of Science®

Sources

PMID: 22151784
PubMed | Europe PMC

Search this title in

Google Scholar