A series of algorithmic results related to the iterated hairpin completion

In this paper we propose efficient algorithmic solutions for the computation of the hairpin completion distance between two given words, for the computation of a minimum-distance common hairpin completion ancestor of two given words (i.e., a word from which we can obtain the two given words by iterated hairpin completion, such that the sum of the hairpin completion distances from this word to the two given words is minimum), and, respectively, for the computation of an arbitrary hairpin completion ancestor of two given words. In all the cases we improve the upper bounds known for time complexity of solving these problems. Then we show how the algorithms designed for these three initial problems can be modified to solve a series of related problems.