2026-08-22T00:37:48Zhttps://docta.ucm.es/rest/oai/request

oai:docta.ucm.es:20.500.14352/1257792025-11-06T01:00:37Zcom_20.500.14352_14col_20.500.14352_15

Phase transition in the computational complexity of the shortest common superstring and genome assembly Fernández Pérez, Luis Antonio Martín Mayor, Víctor Yllanes, D. Genome assembly, the process of reconstructing a long genetic sequence by aligning and merging short fragments, or reads, is known to be NP-hard, either as a version of the shortest common superstring problem or in a Hamiltonian-cycle formulation. That is, the computing time is believed to grow exponentially with the problem size in the worst case. Despite this fact, high-throughput technologies and modern algorithms currently allow bioinformaticians to handle datasets of billions of reads. Using methods from statistical mechanics, we address this conundrum by demonstrating the existence of a phase transition in the computational complexity of the problem and showing that practical instances always fall in the “easy” phase (solvable by polynomialtime algorithms). In addition, we propose a Markov-chain Monte Carlo method that outperforms common deterministic algorithms in the hard regime. 2025-11-05T15:29:44Z 2025-11-05T15:29:44Z 2025-11-05T15:29:44Z 2024-01-24 journal article https://hdl.handle.net/20.500.14352/125779 2470-0045 10.1103/physreve.109.014133 2470-0053 eng info:eu-repo/grantAgreement/AEI/Plan Estatal de Investigación Científica y Técnica y de Innovación 2021-2023/PID2022-136374NB-C21/ES/COMPLEJIDAD EN FISICA Y MAS ALLA: DE LOS VIDRIOS DE ESPIN A LAS INTERACCIONES SOCIALES/ Fernandez, L. A., et al. «Phase Transition in the Computational Complexity of the Shortest Common Superstring and Genome Assembly». Physical Review E, vol. 109, n.o 1, enero de 2024, p. 014133. DOI.org (Crossref), https://doi.org/10.1103/PhysRevE.109.014133 open access American Physical Society