TY - GEN
T1 - Restricting SBH ambiguity via restriction enzymes
AU - Skiena, Steven
AU - Snir, Sagi
N1 - Publisher Copyright:
© Springer-Verlag Berlin Heidelberg 2002.
PY - 2002
Y1 - 2002
N2 - The expected number of n-base long sequences consistent with a given SBH spectrum grows exponentially with n, which severely limits the potential range of applicability of SBH even in an error-free setting. Restriction enzymes (RE) recognize specific patterns and cut the DNA molecule at all locations of that pattern. The output of a restriction assay is the set of lengths of the resulting fragments. By augmenting the SBH spectrum with the target string’s RE spectrum, we can eliminate much of the ambiguity of SBH. In this paper, we build on [20] to enhance the resolving power of restriction enzymes. We give a hardness result for the SBH+RE problem, and supply improved heuristics for the existing backtracking algorithm. We prove a lower bound on the number restriction enzymes required for unique reconstruction, and show experimental results that are not far from this bound.
AB - The expected number of n-base long sequences consistent with a given SBH spectrum grows exponentially with n, which severely limits the potential range of applicability of SBH even in an error-free setting. Restriction enzymes (RE) recognize specific patterns and cut the DNA molecule at all locations of that pattern. The output of a restriction assay is the set of lengths of the resulting fragments. By augmenting the SBH spectrum with the target string’s RE spectrum, we can eliminate much of the ambiguity of SBH. In this paper, we build on [20] to enhance the resolving power of restriction enzymes. We give a hardness result for the SBH+RE problem, and supply improved heuristics for the existing backtracking algorithm. We prove a lower bound on the number restriction enzymes required for unique reconstruction, and show experimental results that are not far from this bound.
UR - https://www.scopus.com/pages/publications/23044532111
U2 - 10.1007/3-540-45784-4_30
DO - 10.1007/3-540-45784-4_30
M3 - Conference contribution
AN - SCOPUS:23044532111
SN - 3540442111
SN - 9783540442110
T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
SP - 404
EP - 417
BT - Algorithms in Bioinformatics - 2nd International Workshop,WABI 2002, Proceedings
A2 - Guigo, Roderic
A2 - Gusfield, Dan
PB - Springer Verlag
T2 - 2nd International Workshop on Algorithms in Bioinformatics, WABI 2002
Y2 - 17 September 2002 through 21 September 2002
ER -