Algorithms for the quantitative Lock/Key model of cytoplasmic incompatibility.

Area of Science:

• Evolutionary Biology
• Computational Biology
• Parasitology

Background:

• Cytoplasmic incompatibility (CI) is a phenomenon where Wolbachia endosymbionts alter host reproduction.
• The precise molecular mechanisms underlying CI are not fully understood.
• Theoretical models, like the Lock-Key model, are crucial for understanding CI dynamics.

Purpose of the Study:

• To model Cytoplasmic incompatibility (CI) using graph theory, specifically the problem of covering bipartite graphs with chain subgraphs.
• To develop and analyze algorithms for finding minimal and maximal chain subgraph covers.
• To address the issue of multiple biologically distinct optimal solutions in CI modeling.

Main Methods:

• Modeling CI as finding minimal chain subgraph covers of a bipartite graph.
• Developing an exponential time algorithm for the NP-hard edge cover problem.
• Designing a quasi-polynomial time algorithm for enumerating all minimal chain subgraph covers.
• Improving algorithms for enumerating maximal chain subgraphs.

Main Results:

• An exponential algorithm for the CI bipartite graph covering problem.
• A quasi-polynomial time algorithm for enumerating all minimal chain subgraph covers.
• Enhanced methods for enumerating maximal chain subgraphs.
• Demonstration of the practical application of these methods on real-world data.

Conclusions:

• The developed algorithms provide new tools for analyzing Cytoplasmic incompatibility (CI) and Wolbachia-host interactions.
• Addressing multiple optimal solutions is critical for accurate biological interpretation.
• The computational approach offers insights into the complex reproductive manipulations driven by parasites.