Student: Shiri Azenkot
School: Pomona College
Project Name: String edit distance with moves
Research Advisor: Dr. Graham Cormode, DIMACS Postdoc
Rutgers University


My name is Shiri Azenkot, and I am currently a Junior at Pomona College in Claremont, CA. I am majoring in computer science, and minoring in math and music. Last summer (2004) I was a participant of the REU (research experience for undergraduates) program at DIMACS. Originally, my research mentor Graham proposed that I explore two project ideas: new wavelet bases, and text comparison of genetic sequences. I mostly focused on the second idea, and I intend to continue my research in this area.

The long term goal of my project is to see how the string edit distance with moves problem can be applied to genetic sequences. So far Iíve implemented a new algorithm that approximates the edit distance with moves between two strings (introduced by Graham Cormode and S. Muthukrishnan) and conducted some tests to evaluate the performance of the algorithm in practice. After conducting more rigorous tests, I will explore the applicability of this algorithm to genetic sequences.

In this website, I have described the algorithm, my implementation, and the results I have compiled thus far. I will continue to update the site with my latest research. If you have any questions about my project, please email me.

Table of Contents

  1. Problem Description
  2. Algorithm Overview
  3. Implementation
  4. Results
  5. Future Research
  6. Acknowledgements
  7. References