On Deriving Synteny Blocks by Compacting Elements.

Authors

Leonard Bohnenkämper, Luca Parmigiani, Kamil Hepak, Cedric Chauve, Jens Stoye

Published in

Journal of computational biology : a journal of computational molecular cell biology. Pages 15578666261491605. Oct 19, 2026. Epub Oct 19, 2026.

Abstract

Genomic rearrangements are major drivers of evolution and genetic disease. Studying rearrangements requires segmenting genomes of interest into conserved regions, called synteny blocks, that highlight structural differences between genomes. Synteny blocks are typically defined from annotated genes or derived as a by-product of whole-genome alignment. However, as these procedures are heuristic and do not explicitly model rearrangements, they can obscure real variation, create false similarities, and affect phylogenetic inference. We present a formal framework for deriving synteny blocks by partitioning genomic elements into blocks that do not contain breakpoints. A breakpoint is defined between a pair of genomes as an adjacency of shared elements that occurs in one genome but not in the other. Synteny blocks are therefore not allowed to span such boundaries, ensuring that rearrangements are not obscured. The framework is fully agnostic to the type of genomic element and applies to any genome representation expressed as sequences of elements, such as nonoverlapping alignments, exact matches (MUMs/MEMs), k-mers, unitigs, or minimizers. We formalize two optimization problems: minimizing the total genome length after replacement by synteny blocks (the Minimum-Length Synteny Block Problem) and minimizing the number of distinct blocks (the Minimum-Size Synteny Block Problem). We show that both problems are NP-hard in general. However, when blocks are required to be collinear and to contain a shared element, we provide a linear-time algorithm with respect to the number of input elements that simultaneously minimizes both objectives. The resulting method is simple, efficient, and produces large synteny blocks without obscuring rearrangements.

PMID:
42895109
Bibliographic data and abstract were imported from PubMed on 19 Oct 2026.

Read full publication at:
Please sign in to see all details.

Stats

1-terrible, 9-excellent. How would you rate this publication? Sign in in to submit your rating.

Post a comment

You need to be signed in to post comments. You can sign in here.

Comments

There are no comments yet.