Report icon

Report

Local Uniqueness of Alignments with a Fixed Proportion of Gaps

Abstract:
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.

Actions


Access Document


Files:

Authors


Raphael Hauser More by this author
Heinrich Matzinger More by this author
Publication date:
2005-05-05
URN:
uuid:381171a2-ad03-46a7-ab3e-d9cf6d5ecfd4
Local pid:
oai:eprints.maths.ox.ac.uk:1145

Terms of use


Metrics



If you are the owner of this record, you can report an update to it here: Report update to this record

TO TOP