Integer linear programming for phylogenetic tree inference in multi-state mixtures

Enayatsefat, Raziyeh; Bagherian, Mehri; Vaziri, Hamidreza

doi:10.22124/jmm.2026.33204.3025

Integer linear programming for phylogenetic tree inference in multi-state mixtures

Articles in Press

Document Type : Research Article

Authors

¹ Department of Applied Mathematics, Faculty of Mathematical Sciences, University of Guilan, Rasht, Iran

² Department of Biology, Faculty of Sciences, University of Guilan, Rasht, Iran

10.22124/jmm.2026.33204.3025

Abstract

The evolutionary history of somatic mutations within cells, which plays a key role in the development of cancer, can be represented using a phylogenetic tree. Studying the evolution of mutations is crucial for advancing cancer treatment. In this study, we address the problem of reconstructing phylogenetic trees from mixed populations of cells, modeled as the cladistic multi-state Perfect Phylogeny Mixture Deconvolution Problem (PPMDP). Given the frequency measurements of character states across bulk samples, the objective is to infer a tree that satisfies Infinite-Alleles Assumption (IAA). To this aim, we propose a Binary Linear Programming (BLP) formulation. The method incorporates both Single-Nucleotide Variations (SNVs) and Copy Number Variations (CNVs) as input data. We evaluate the approach using simulated and real data, and demonstrate that the BLP model reconstructs phylogenetic trees efficiently and accurately, showing high coincidence with the ground truth trees.

Keywords