Rxivist logo

The Homo-Edit Distance Problem

By Maren Brand, Nguyen Khoa Tran, Philipp Spohr, Sven Schrinner, Gunnar W. Klau

Posted 30 May 2020
bioRxiv DOI: 10.1101/2020.05.27.118273

We consider the homo-edit distance problem, which is the minimum number of homo-deletions or homo-insertions to convert one string into another. A homo-insertion is the insertion of a string of equal characters into another string, while a homo-deletion is the inverse operation. We show how to compute the homo-edit distance of two strings in polynomial time: We first demonstrate that the problem is equivalent to computing a common subsequence of the two input strings with a minimum number of homo-deletions and then present a dynamic programming solution for the reformulated problem. ### Competing Interest Statement The authors have declared no competing interest.

Download data

  • Downloaded 110 times
  • Download rankings, all-time:
    • Site-wide: 94,389 out of 103,749
    • In bioinformatics: 8,892 out of 9,474
  • Year to date:
    • Site-wide: 63,115 out of 103,749
  • Since beginning of last month:
    • Site-wide: 52,300 out of 103,749

Altmetric data

Downloads over time

Distribution of downloads per paper, site-wide


Sign up for the Rxivist weekly newsletter! (Click here for more details.)