Several variants of the edit distance problem with block deletions are considered. Polynomial time optimal algorithms are presented for the edit distance with block deletions allowing character insertions and character moves, but without block moves. We show that the edit distance with block moves and block deletions is NP-complete (Nondeterministic Polynomial time problems in which any given solution to such problem can be verified in polynomial time, and any NP problem can be converted into it in polynomial time), and that it can be reduced to the problem of non-recursive block moves and block deletions within a constant factor.
References
[1]
Gusfield, D. Algorithms on Strings, Trees, and Sequences: Computer Science and Computational Biology; Press Syndicate of the University of Cambridge: New York, NY, USA, 2007.
[2]
Masek, W.J.; Paterson, M.S. A Faster Algorithm for Computing String Edit Distances. J. Comput. Syst. Sci. Int. 1980, 20, 18–31, doi:10.1016/0022-0000(80)90002-1.
[3]
Crochemore, M.; Landau, G.M.; Ziv-ukelson, M. A sub-quadratic sequence alignment algorithm for unrestricted cost matrices. SIAM J.Comput. 2003, 32, 1654–1673, doi:10.1137/S0097539702402007.
[4]
Shapira, D.; Storer, J.A. Edit Distance with Move Operations. J. Discrete Algorithms 2007, 5, 380–392, doi:10.1016/j.jda.2005.01.010.
[5]
Ukkonen, E. Algorithms for approximate string matching. Inf. Control 1985, 64, 100–118, doi:10.1016/S0019-9958(85)80046-2.
[6]
Ann, Y.; Peng, L. Efficient algorithms for the block-edit problems. Inf. Comput. 2010, 208, 221–229, doi:10.1016/j.ic.2009.12.001.
[7]
Muthukrishnan, S.; Sahinalp, S.C. Approximate Nearest Neighbors and Sequence Comparison with Block Operations. Proceeding of the Thirty-Second Annual ACM Symposium on Theory of Computing; ACM Press: New York, NY, USA, 2000; pp. 416–424.
Cormode, G.; Muthukrishnan, S. The String Edit Distance Matching Problem with Moves. ACM Trans. Algorithms 2007, 3, doi:10.1145/1186810.1186812.
[10]
Cormode, G.; Paterson, M.; Sahinalp, S.C.; Vishkin, U. Communication Complexity of Document Exchange. In Symp., Proceedings of the Eleventh Annual ACM-SIAM Symposium on Discrete Algorithms; Society for Industrial and Applied Mathematics: Philadelphia, PA, USA, 2000; pp. 197–206.
[11]
Ergun, F.; Muthukrishnan, S.; Sahinalp, S.C. Comparing Sequences with Segment Rearrangements. Lect. Notes in Comput. Sci. 2003, 2914, 183–194.
[12]
Chrobak, M.; Kolman, P.; Sgall, J. The Greedy Algorithm for the Minimum Common String Partition Problem. ACM Trans. Algorithms 2004, 1, 84–95.
[13]
Shafrir, N.; Kaplan, H. The Greedy Algorithm for Edit Distance with Moves. Inf. Process. Lett. 2006, 1, 23–27.
[14]
Bafna, V.; Pevzner, P. A. Sorting by Transpositions. SIAM J. Discrete Math. 199, 11, 124–240.
[15]
Lopresti, D.; Tomkins, A. Block Edit Models for Approximate String Matching. Theor. Comput. Sci. 1997, 181, 159–179, doi:10.1016/S0304-3975(96)00268-X.
[16]
Tichy, W.F. The String to String Correction Problem with Block Moves. ACM Trans. Comput. Syst. 1984, 2, 309–321, doi:10.1145/357401.357404.
[17]
Hannenhalli, S. Polynomial-Time Algorithm for Computing Translocation Distance between Genomes. Discrete Appl. Math. 1996, 71, 137–151, doi:10.1016/S0166-218X(96)00061-3.
[18]
Durand, D.; Farach, M.; Ravi, R.; Singh, M. A Short Course in Computational Molecular Biology. DIMACS Technical Report 97-63; Center for Discrete Mathematics & Theoretical Computer Science: Piscataway, NJ, USA, 1997.
[19]
Smith, T.F.; Waterman, M.S. Identification of Common Molecular Sequences. J. Mol. Biol. 1981, 147, 195–197, doi:10.1016/0022-2836(81)90087-5. 7265238
[20]
Hermelin, D.; Landau, G.M.; Landau, S.; Weimann, O. A Unified Algorithm for Accelerating Edit-Distance Computation via Text-Compression. Symp. Theor. Aspects Comput. Sci. 2009 2009, 529–540.
