Labeled Cycle Graph for Transposition and Indel Distance.

Area of Science:

• Comparative genomics
• Bioinformatics
• Computational biology

Background:

• Inferring evolutionary distance between species relies on quantifying genome rearrangements.
• Genome rearrangements are large-scale mutations transforming one genome into another, with distance measured by the minimum number of mutations.
• Early research focused on conservative rearrangements (reversals, transpositions) between genomes with identical gene content.

Purpose of the Study:

• To address the challenge of calculating rearrangement distance for genomes with unequal gene content.
• To investigate the transposition and indel distance, a computationally difficult problem (NP-hard).
• To introduce a novel structure for representing genome rearrangement instances with non-conservative mutations.

Main Methods:

• Introduction of a labeled cycle graph structure to model genomes with unequal gene content.
• Utilizing the labeled cycle graph to derive a lower bound for the transposition and indel distance.
• Development of a 2-approximation algorithm based on the labeled cycle graph for the transposition and indel distance.

Main Results:

• The labeled cycle graph effectively represents instances of rearrangement distance problems involving unequal gene content.
• A novel lower bound for the transposition and indel distance was established.
• A 2-approximation algorithm was successfully devised for the transposition and indel distance.

Conclusions:

• The labeled cycle graph is a valuable tool for analyzing genome rearrangements with insertions and deletions (indels).
• The study provides a practical approach to approximating the transposition and indel distance, crucial for comparative genomics.
• This work advances the understanding of evolutionary distances in the context of genomes with differing gene sets.