An approach combining classical and quantum computing to address the complexity of reconstructing phylogenetic trees from genetic data
CRS4 will participate in CIBB 2026 – the 21st International Conference on Computational Intelligence Methods for Bioinformatics and Biostatistics, taking place from 2 to 4 September 2026 at Sapienza University of Rome, where it will present a study exploring the use of quantum optimization methods to investigate evolutionary relationships among human populations.
The starting point is the differences found in DNA. By comparing a large number of genetic variants, it is possible to reconstruct relationships among different samples and represent them through a phylogenetic tree, a representation similar to a family tree that describes how groups of organisms are evolutionarily related.
Identifying the tree that best represents the available data is, however, a highly complex computational problem: as the number of elements considered increases, the number of possible solutions grows dramatically. The CRS4 study proposes a method for addressing this challenge by breaking the problem down into smaller subproblems, which can be solved separately and subsequently recombined. The aim is to make this type of computation compatible with the still limited capabilities of current quantum computing systems.
The method was tested using existing genomic data from the Y chromosome, analysing more than 128,000 genetic variants. The procedure made it possible to reconstruct a tree representing evolutionary relationships, achieving results comparable to those obtained with a classical reference method. At this stage, the quantum algorithms were run on a simulator.
The study, entitled “A Block Decomposed QUBO Workflow for Chromosome-Y Phylogeny Reconstruction”, was carried out by CRS4 researchers Giuliana Siddi Moreau, Riccardo Berutti, Manuela Profir, Lorenzo Pisani, Maria Laura Clemente and Lidia Leoni.
Future developments outlined by the authors include testing the method on real quantum processors, using both superconducting and trapped-ion technologies, and comparing its performance with classical methods for phylogenetic tree reconstruction.
The work was carried out within the institutional project QCC & HPC – Quantum Computation and Communication – High Performance Computing, funded by the Autonomous Region of Sardinia through Sardegna Ricerche, with a contribution pursuant to Article 9 of Regional Law No. 20/2015.
The contribution will be presented on Thursday, 3 September, as part of CIBB 2026 Special Session SS16, “Quantum Artificial Intelligence for Bioinformatics and Biostatistics: Theory, Algorithms, and Applications”.
In the image: the screen displays a diagram of the procedure developed by CRS4 researchers, showing the different stages of the process, from Y-chromosome genetic data to the reconstruction of the phylogenetic tree, combining classical computing methods and quantum optimization.
