title: Simplified partial digest problem: enumerative and dynamic programming algorithms.
abstract: 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 and an O(n(2q)) time dynamic programming algorithm for the error-free SPDP, where $n$ is the number of restriction sites and n is the number of distinct intersite distances. We also give examples of the problem, in which there are 2(n+2)/(3)-1 non-congruent solutions. These examples partially answer a question recently posed in the literature about the number of solutions of SPDP. We adapt our enumerative algorithm for handling SPDP with imprecise input data. Finally, we describe and discuss the results of the computer experiments with our algorithms.
authors.affiliation: Institute of Computer Sceince, Poznan University of Technology, Poznan, Poland. jblazewicz@cs.put.poznan.pl
authors.forename: Jacek
authors.initials: J
authors.lastname: Blazewicz
authors.forename: Edmund
authors.initials: E
authors.lastname: Burke
authors.forename: Marta
authors.initials: M
authors.lastname: Kasprzak
authors.forename: Alexandr
authors.initials: A
authors.lastname: Kovalev
authors.forename: Mikhail
authors.initials: M
authors.lastname: Kovalyov
mesh_terms: D000465:Algorithms; D019295:Computational Biology / Q000379:methods*; D004247:DNA / Q000737:chemistry; D016678:Genome; D015233:Models, Statistical; D008962:Models, Theoretical; D011381:Programming Languages; D015203:Reproducibility of Results; D012984:Software
chemical_list: D004247:DNA