Mgenome

Mgenome solves the multiple genome rearrangement problem by modeling genomes as signed permutations and computing collections of genomes connected by signed reversals that minimize the total number of signed reversals (Steiner tree formulation).

Key Features:

• Problem Modeling: Models genomes as signed permutations on genes and formulates the multiple genome rearrangement task as finding reversal paths that minimize the total number of signed reversals, an NP-hard problem equivalent to an optimal Steiner tree connecting genomes.
• Neighbor-Perturbing Algorithm (approximation): A polynomial-time approximation algorithm that iteratively perturbs initial Steiner node candidates within their neighborhoods to identify and refine candidate optimal Steiner nodes until convergence.
• Branch-and-Bound Algorithm (exact): An exponential-time exact algorithm that addresses the median problem by evaluating candidate solutions that satisfy specified necessary conditions for optimality.
• Implementation and Performance: The algorithms are implemented as two distinct programs, and experimental comparisons reported show performance advantages relative to GRAPPA, BPAnalysis, and MGR.

Scientific Applications:

• Evolutionary biology: Infer parsimonious reversal scenarios to study genomic structural changes and evolution across species.
• Ancestral genome reconstruction: Reconstruct ancestral genomes by minimizing the number of signed reversals required to connect extant genomes.
• Comparative genomics: Analyze structural variations and rearrangement distances between genomes represented as signed permutations.
• Computational biology research: Provide algorithmic approaches and benchmarks for the median problem and multiple genome rearrangement studies.

Methodology:

Models genomes as signed permutations and formulates the problem as a minimum-cost Steiner tree under signed reversals; employs a polynomial-time neighbor-perturbing approximation algorithm and an exponential-time branch-and-bound exact algorithm for the median problem, implemented in two programs that evaluate candidate solutions satisfying necessary optimality conditions.