The distance and median problems in the single-cut-or-join model with single-gene duplications.

Conclusion: Our results provide a simple genome rearrangement model, extending the SCJ model to account for single-gene duplications, for which we prove a mix of tractability and hardness results. For the NP-complete rooted median problem, we design a simple Integer Linear Program. Our publicly available implementation of these algorithms for the directed distance and median problems allow to solve efficiently these problems on large instances. PMID: 32391071 [PubMed]
Source: Algorithms for Molecular Biology : AMB - Category: Molecular Biology Authors: Tags: Algorithms Mol Biol Source Type: research