Sorting Signed Permutations by Reversals in Nearly-Linear Time

fewest reversals. This is a fundamental algorithmic problem motivated
by applications in comparative genomics, as it allows to accurately
model rearrangements in small genomes. The first polynomial-time
algorithm was given in the foundational work of Hannenhalli and
Pevzner [J. ACM'99]. Their approach was later streamlined and
simplified by Kaplan, Shamir, and Tarjan [SIAM J. Comput.'99] and
their framework has eventually led to an algorithm that works in
O(n^1.5 sqrt(log(n))) time given by Tannier, Bergeron, and Sagot
[Discr. Appl. Math.'07]. However, the challenge of finding a
nearly-linear time algorithm remained unresolved. In this paper, we
show how to leverage the results on dynamic graph connectivity to
obtain a surprisingly simple O(nlog2n/loglogn) time algorithm for this
problem.

Joint work with Bartłomiej Dudek and Tatiana Starikovskaya, published
in SOSA@SODA 2024.