000148286 001__ 148286
000148286 005__ 20250923084413.0
000148286 0247_ $$2doi$$a10.1103/PhysRevE.109.014133
000148286 0248_ $$2sideral$$a137671
000148286 037__ $$aART-2024-137671
000148286 041__ $$aeng
000148286 100__ $$aFernandez, L. A.
000148286 245__ $$aPhase transition in the computational complexity of the shortest common superstring and genome assembly
000148286 260__ $$c2024
000148286 5060_ $$aAccess copy available to the general public$$fUnrestricted
000148286 5203_ $$aGenome 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 polynomial-time algorithms). In addition, we propose a Markov-chain Monte Carlo method that outperforms common deterministic algorithms in the hard regime.
000148286 536__ $$9info:eu-repo/grantAgreement/ES/MICINN AEI/PID2022-136374NB-C21
000148286 540__ $$9info:eu-repo/semantics/openAccess$$aAll rights reserved$$uhttp://www.europeana.eu/rights/rr-f/
000148286 590__ $$a2.4$$b2024
000148286 592__ $$a0.705$$b2024
000148286 591__ $$aPHYSICS, MATHEMATICAL$$b13 / 61 = 0.213$$c2024$$dQ1$$eT1
000148286 593__ $$aCondensed Matter Physics$$c2024$$dQ2
000148286 591__ $$aPHYSICS, FLUIDS & PLASMAS$$b17 / 41 = 0.415$$c2024$$dQ2$$eT2
000148286 593__ $$aStatistics and Probability$$c2024$$dQ2
000148286 593__ $$aStatistical and Nonlinear Physics$$c2024$$dQ2
000148286 655_4 $$ainfo:eu-repo/semantics/article$$vinfo:eu-repo/semantics/acceptedVersion
000148286 700__ $$0(orcid)0000-0002-3376-0327$$aMartin-Mayor, V.
000148286 700__ $$0(orcid)0000-0001-7276-2942$$aYllanes, D.
000148286 773__ $$g109, 1 (2024), 014133 [8 pp.]$$pPhys. rev., E$$tPhysical Review E$$x2470-0045
000148286 8564_ $$s844331$$uhttps://zaguan.unizar.es/record/148286/files/texto_completo.pdf$$yPostprint
000148286 8564_ $$s3317064$$uhttps://zaguan.unizar.es/record/148286/files/texto_completo.jpg?subformat=icon$$xicon$$yPostprint
000148286 909CO $$ooai:zaguan.unizar.es:148286$$particulos$$pdriver
000148286 951__ $$a2025-09-22-14:31:28
000148286 980__ $$aARTICLE