Reproduce “Complexity and Enumeration in Models of Genome Rearrangement” on OpenResearch
Turn your favorite coding agents into research agents that review literature, develop hypotheses, and run experiments.
Universal app for Apple silicon and Intel. Requires macOS 11 or later.
About this paper
Lora Bailey, Heather Smith Blake, Garner Cochran, Nathan Fox, Michael Levet, Reem Mahmoud, Elizabeth Matson, Inne Singgih and 3 more
This research establishes that counting most parsimonious genome rearrangement scenarios in the Single Cut-and-Join (SCaJ) model is #P-complete, demonstrating its computational intractability. Concurrently, it refines the complexity of enumerating median genomes in the Single Cut or Join (SCoJ) model from polynomial time (FP) to the more efficient logarithmic space (FL).
Key insights
- Even restricted cases of counting most parsimonious scenarios in the SCaJ model (i.e., when adjacency graphs consist only of crowns) are #P-complete, indicating their inherent computational intractability for exact solutions.
- The #Median problem in the SCoJ model is significantly more efficient than previously understood, being solvable with highly limited memory resources (FL).
- Precise formulas and modular arithmetic can be leveraged to count complex combinatorial structures, such as distinct sorting scenarios for collections of crowns, despite the problem's overall hardness.
Summary by alphaXiv.
Tip: change arxiv.org to autoarxiv.org in any arXiv abstract link to open the paper here.