A partial digest approach to restriction site mapping |
| |
Authors: | Steven S Skiena Gopalakrishnan Sundaram |
| |
Institution: | (1) Department of Computer Science, State University of New York, 11794 Stony Brook, NY, U.S.A.;(2) Centre de Recherches Mathematiques (CRM), Universite de Montreal, C.P. 6128, H3C 3J7 Succursale A, Montreal, Canada |
| |
Abstract: | We present a new, practical algorithm to resolve the experimental data in restriction site analysis, which is a common technique
for mapping DNA. Specifically, we assert that multiple digestions with a single restriction enzyme can provide sufficient
information to identify the positions of the restriction sites with high probability. The motivation for the new approach
comes from combinatorial results on the number of mutually homeometric sets in one dimension, where two sets ofn points are homeometric if the multiset ofn(n−1)/2 distances they determine are the same.
Since experimental data contain errors, we propose algorithms for reconstructing sets from noisy interpoint distances, including
the possibility of missing fragments. We analyse the performance of these algorithms under a reasonable probability distribution,
establishing a relative error limit ofr=Θ(1/n
2) beyond which our technique becomes infeasible. Through simulations, we establish that our technique is robust enough to
reconstruct data with relative errors of up to 7.0% in the measured fragment lengths for typical problems, which appears sufficient
for certain biological applications. |
| |
Keywords: | |
本文献已被 SpringerLink 等数据库收录! |
|