The Intersection of Insertion and Deletion Balls

Authors

Image provided by Daniella Bar-Lev
Daniella
Bar-Lev
Technion
Profile
Omer
Sabary
University of California, San Diego
Profile
Yotam
Gershon
Technion - Israel Institute of Technology
Profile
Eitan
Yaakobi
Technion

Abstract

This paper studies the intersections of insertion and deletion balls. The t-insertion, t-deletion ball of a sequence x is the set of all sequences received by t insertions, deletions to x, respectively. While the intersection of either deletion balls or insertion balls has been rigorously studied before, the intersection of an insertion ball and a deletion ball has not been addressed so far. We find the maximum intersection size of any two insertion and deletion balls in the binary case. For the special case of one-insertion and one-deletion balls we find the intersection size for all pair of sequences. Then, we derive the largest and average values of this intersection size. Lastly, we present an algorithm that efficiently computes the intersection of any t1-insertion ball and t2-deletion ball.

Paper Manuscript