Local Uniqueness of Alignments with a Fixed Proportion of Gaps
- We consider two independent random strings with i.i.d. characters and examine their optimal alignments containing a fixed proportion of gaps. We prove that when the proportion of gaps is small then with high probability optimal alignments differ only in a small number of places and are locally unique everywhere else. The result is somewhat surprising, as one might expect unrelated sequences to admit many near-optimal alignments, whereas for related sequences one might expect an optimal alignment that is unique in many places.
- Publication date:
- Local pid:
- Copyright date: