TY  - JOUR
AB  - 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.
DA  - 2011
DO  - 10.1186/1471-2105-12-S9-S13
LA  - eng
IS  - Suppl 9: RECOMB-CG 2011
PY  - 2011
SN  - 1471-2105
T2  - BMC Bioinformatics
TI  - On the weight of indels in genomic distances
UR  - https://nbn-resolving.org/urn:nbn:de:0070-pub-23965589
Y2  - 2024-11-21T16:01:23
ER  -