ICALP best paper award for Ahmed's multistrand MFE algorithm

Ahmed presented our paper at a joint session of ICALP 2025 at Aarhus University, Denmark, where he received the best paper award. Congrats to Ahmed!

The paper: An efficient algorithm to compute the minimum free energy of interacting nucleic acid strands, Ahmed Shalaby, Damien Woods. LIPIcs vol. 334, pp. 130:1-130:20. ICALP 2025. It gives the first polynomial time algorithm to compute the most favoured secondary structure of a collection of DNA or RNA strands. Such a structure is called a minimum free energy (MFE) structure.

There is a several-decade history to this problem, starting with simple models of DNA/RNA binding, and leading to two important papers: In a SIAM Review paper in 2007, Dirks, Bois, Schaeffer, Winfree and Pierce gave a polynomial time algorithm to find the partition function for a small set of strands, a related problem. However, they left MFE as an open problem. That paper, and others, underlie popular software packages that handle multiple strands, such as NUPACK and ViennaRNA. However, for a large set of strands, large enough to be on a par with the total number of DNA/RNA bases, Condon, Hajiaghayi and Thachuk [DNA27, 2021] showed that MFE is NP-complete, meaning it is unlikely to have a fast algorithm. Our paper shows that if the number of strands is small, as in Dirks et al, there is in fact a polynomial time algorithm. Specifically, the algorithm handles the case of multiple identical strands, a setting which induces a rotational symmetry penalty that was awkward to handle with previous techniques.