Genomic Distance with High Indel Costs

Area of Science:

• Computational Biology
• Bioinformatics
• Genomics

Background:

• The DCJ-indel distance is a metric for genome rearrangements.
• Understanding its computational complexity is crucial for phylogenetic analysis.
• Previous methods may not efficiently handle distinct costs for different operations.

Purpose of the Study:

• To determine the computational complexity of the DCJ-indel distance.
• To develop an efficient method for calculating this distance with variable operation costs.
• To address the issue of triangular inequality disruption in DCJ-indel metrics.

Main Methods:

• Derivation of an exact formula for DCJ-indel distance.
• Analysis of computational complexity, aiming for linear time.
• Development of an efficient algorithmic correction for triangular inequality.

Main Results:

• An exact formula for DCJ-indel distance computation in linear time was established.
• The formula accommodates arbitrary constant costs for DCJ and indel operations.
• An efficient algorithm was proposed to correct triangular inequality violations.

Conclusions:

• The DCJ-indel distance can be computed efficiently, even with distinct operation costs.
• The proposed correction method enhances the reliability of DCJ-indel metrics.
• This work provides a computationally feasible approach for evolutionary distance calculations.