کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
435574 | 689916 | 2010 | 17 صفحه PDF | دانلود رایگان |
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.
Journal: Theoretical Computer Science - Volume 411, Issue 48, 1 November 2010, Pages 4162-4178