Multi-sample bulk DNA sequencing enables reconstruction of a tumor’s clonal history, but scalable methods often rely on heuristic search and provide no optimality guarantees. We present CITUP2, an integrative combinatorial optimization framework that reconstructs clonal trees from descendant cell fractions (DCFs) of mutational clusters. CITUP2 formulates tree inference as a mixed-integer quadratic program (MIQP) that jointly determines the tree topology and clone prevalences across samples. It minimizes a weighted discrepancy between observed and inferred DCFs, with options to prioritize trees exhibiting consistency in the presence-absence patterns of parent-child clones. Under this formulation, CITUP2 returns provably optimal solutions (with respect to the model) and avoids the combinatorial explosion of exhaustive topology enumeration used by existing methods with optimality guarantees. In addition, CITUP2 can report a user-specified number of best trees. In simulations and analyses of a large, recently published multi-sample TRACERx cohort, CITUP2 scales to trees with tens of clones (approximately 30) and matches or improves on the fit attained by state-of-the-art approaches, while providing clear optimality certificates. Salem Malikic, Hamza Iseric, Chih Hao Wu, Erin Molloy, S. Cenk Sahinalp. Reconstruction of Tumor Clonal Trees with Multi-Sample Bulk Sequencing Data by Integrative Combinatorial Optimization [abstract]. In: Proceedings of the American Association for Cancer Research Annual Meeting 2026; Part 1 (Regular Abstracts); 2026 Apr 17-22; San Diego, CA. Philadelphia (PA): AACR; Cancer Res 2026;86(7 Suppl):Abstract nr 6905.

The increasing availability of high-quality genome assemblies raised interest in the characterization of genomic architecture. Major architectural elements, such as common repeats and segmental duplications (SDs), increase genome plasticity that stimulates further evolution by changing the genomic structure and inventing new genes. Optimal computation of SDs within a genome requires quadratic-time local alignment algorithms that are impractical due to the size of most genomes. Additionally, to perform evolutionary analysis, one needs to characterize SDs in multiple genomes and find relations between those SDs and unique (non-duplicated) segments in other genomes. A naïve approach consisting of multiple sequence alignment would make the optimal solution to this problem even more impractical. Thus there is a need for fast and accurate algorithms to characterize SD structure in multiple genome assemblies to better understand the evolutionary forces that shaped the genomes of today. Here we introduce a new approach, BISER, to quickly detect SDs in multiple genomes and identify elementary SDs and core duplicons that drive the formation of such SDs. BISER improves earlier tools by (i) scaling the detection of SDs with low homology to multiple genomes while introducing further 7–33×\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\times$$\end{document} speed-ups over the existing tools, and by (ii) characterizing elementary SDs and detecting core duplicons to help trace the evolutionary history of duplications to as far as 300 million years. BISER is implemented in Seq programming language and is publicly available at https://github.com/0xTCG/biser.