logo
CanyamAI summaries for academic research
language
MobileMobile
  • Phone FeatureWeChat Mini Program
EnglishEnglish
noticeNotice
BlogBlog
delete
arrow
Return

The simplified partial digest problem: Enumerative and dynamic programming algorithms

delete2007-10-01
delete11
PRE
AI
J
Jacek Błażewicz *
E
Edmund Burke
M
Marta Kasprzak
A
A. Kovalev
M
Mikhail Y. Kovalyov
DOI：10.1109/TCBB.2007.1060delete
deleteOriginal
deleteOriginal request for help
deleteShare
deleteSave
Abstract

Abstract

En 中文
We study the Simplified Partial Digest Problem ( SPDP), which is a mathematical model for a new simplified partial digest method of genome mapping. This method is easy for laboratory implementation and robust with respect to the experimental errors. SPDP is NP-hard in the strong sense. We present an O(n2(n)) time enumerative algorithm (ENUM) and an O(n(2q)) time dynamic programming algorithm for the error-free SPDP, where n is the number of restriction sites and q is the number of distinct intersite distances. We also give examples of the problem in which there are 2(n+2/3-1) noncongruent solutions. These examples partially answer a question recently posed in the literature about the number of solutions of SPDP. We adapt our ENUM for handling SPDP with imprecise input data. Finally, we describe and discuss the results of the computer experiments with our algorithms.
Keywords:
algorithm design and analysis
dynamic programming
genome mapping
restriction site analysis
imprecise information
AI Summary

AI Summary

Key information extracted from the uploaded paper, including a brief overview, abstract, background, key highlights, visual analysis, and future outlook.

Journal

I
IEEE-ACM Transactions on Computational Biology and Bioinformatics
IF:
3.4
Papers:
3.3K
Citations:
6.4K

Organization

No organization information available