<p>Computing the energy barrier between RNA structures is a classic NP-hard problem in bioinformatics, of which the Independent Set (IS) reconfiguration in bipartite graphs represents a natural generalization. Parameterized algorithms, based on parameters taking limited or bounded values on biological instances, are thus crucial towards practical solutions. In this work, we show that bipartite IS reconfiguration is slice-wise Polynomial (XP) solvable for both the range <InlineEquation ID="IEq1"> <EquationSource Format="TEX">$\rho $</EquationSource> <EquationSource Format="MATHML"><math> <mi>ρ</mi> </math></EquationSource> </InlineEquation> of IS sizes allowed along the reconfiguration, and the arboricity <InlineEquation ID="IEq2"> <EquationSource Format="TEX">$\Phi $</EquationSource> <EquationSource Format="MATHML"><math> <mi mathvariant="normal">Φ</mi> </math></EquationSource> </InlineEquation> when the input is restricted to a circle graph. Such a setting is relevant to Bioinformatics as it provides a solution to the RNA energy barrier problem. We propose algorithms based on a divide-and-conquer approach, yielding a <InlineEquation ID="IEq3"> <EquationSource Format="TEX">$O\left( n^{2}\right) $</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi>O</mi> <mfenced close=")" open="("> <msup> <mi>n</mi> <mn>2</mn> </msup> </mfenced> </mrow> </math></EquationSource> </InlineEquation>-space, <InlineEquation ID="IEq4"> <EquationSource Format="TEX">$O\left( n^{2\rho +2.5}\right) $</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi>O</mi> <mfenced close=")" open="("> <msup> <mi>n</mi> <mrow> <mn>2</mn> <mi>ρ</mi> <mo>+</mo> <mn>2.5</mn> </mrow> </msup> </mfenced> </mrow> </math></EquationSource> </InlineEquation>-time algorithm for the range <InlineEquation ID="IEq5"> <EquationSource Format="TEX">$\rho $</EquationSource> <EquationSource Format="MATHML"><math> <mi>ρ</mi> </math></EquationSource> </InlineEquation>, and a <InlineEquation ID="IEq6"> <EquationSource Format="TEX">$O\left( n^{\Phi + 2}\right) $</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi>O</mi> <mfenced close=")" open="("> <msup> <mi>n</mi> <mrow> <mi mathvariant="normal">Φ</mi> <mo>+</mo> <mn>2</mn> </mrow> </msup> </mfenced> </mrow> </math></EquationSource> </InlineEquation>-space, <InlineEquation ID="IEq7"> <EquationSource Format="TEX">$O\left( n^{\Phi +3}\right) $</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi>O</mi> <mfenced close=")" open="("> <msup> <mi>n</mi> <mrow> <mi mathvariant="normal">Φ</mi> <mo>+</mo> <mn>3</mn> </mrow> </msup> </mfenced> </mrow> </math></EquationSource> </InlineEquation>-time algorithm for the arboricity <InlineEquation ID="IEq8"> <EquationSource Format="TEX">$\Phi $</EquationSource> <EquationSource Format="MATHML"><math> <mi mathvariant="normal">Φ</mi> </math></EquationSource> </InlineEquation>. We demonstrate the practicality of our algorithms on benchmarks respectively consisting of random Erdös-Rényi bipartite graphs, random pairs of RNA structures and experimentally-supported instances of RNA kinetics.</p>

Bipartite Independent Set Reconfiguration: General and RNA-Inspired Parameterized Algorithms

期刊论文
发表日期：

2026年3月5日

查看全文

Théo Boury,
Laurent Bulteau,
Bertrand Marchand,
Yann Ponty

摘要

Computing the energy barrier between RNA structures is a classic NP-hard problem in bioinformatics, of which the Independent Set (IS) reconfiguration in bipartite graphs represents a natural generalization. Parameterized algorithms, based on parameters taking limited or bounded values on biological instances, are thus crucial towards practical solutions. In this work, we show that bipartite IS reconfiguration is slice-wise Polynomial (XP) solvable for both the range $\rho $ $ρ$ of IS sizes allowed along the reconfiguration, and the arboricity $\Phi $ $Φ$ when the input is restricted to a circle graph. Such a setting is relevant to Bioinformatics as it provides a solution to the RNA energy barrier problem. We propose algorithms based on a divide-and-conquer approach, yielding a $O\left( n^{2}\right) $ $O (n^{2})$ -space, $O\left( n^{2\rho +2.5}\right) $ $O (n^{2 ρ + 2.5})$ -time algorithm for the range $\rho $ $ρ$ , and a $O\left( n^{\Phi + 2}\right) $ $O (n^{Φ + 2})$ -space, $O\left( n^{\Phi +3}\right) $ $O (n^{Φ + 3})$ -time algorithm for the arboricity $\Phi $ $Φ$ . We demonstrate the practicality of our algorithms on benchmarks respectively consisting of random Erdös-Rényi bipartite graphs, random pairs of RNA structures and experimentally-supported instances of RNA kinetics.