DNA expressions - A formal notation for DNA

Leiden Repository

DNA expressions - A formal notation for DNA

Type: Doctoral Thesis
Title: DNA expressions - A formal notation for DNA
Author: Vliet, Rudy van
Publisher: Leiden Institute of Advanced Computer Science (LIACS), Faculty of Science, Leiden University
Issue Date: 2015-12-10
Keywords: Minimal DNA expressions
Combinatorics
Normal form
Algorithms
Complexity
DNA computing
Abstract: We describe a formal notation for DNA molecules that may contain nicks and gaps. The resulting DNA expressions denote formal DNA molecules. Different DNA expressions may denote the same molecule. Such DNA expressions are called equivalent. We examine which DNA expressions are minimal, which means that they have the shortest length among all equivalent DNA expressions. Among others, we describe how to construct a minimal DNA expression for a given molecule. We also present an efficient, recursive algorithm to rewrite a given DNA expression into an equivalent, minimal DNA expression. For many formal DNA molecules, there exists more than one minimal DNA expression. We define a minimal normal form, i.e., a set of properties such that for each formal DNA molecule, there is exactly one (minimal) DNA expression with these properties. We finally describe an efficient, two-step algorithm to rewrite an arbitrary DNA expression into this normal form.
Description: Promotores: J.N. Kok, H.J. Hoogeboom
With Summary in Dutch
Faculty: Faculteit der Wiskunde en Natuurwetenschappen
Citation: Vliet, R. van, 2015, Doctoral Thesis, Leiden University
Series/Report no.: IPA Dissertation Series; 2015-23
ISBN: 9789462992542
Handle: http://hdl.handle.net/1887/37052
 

Files in this item

Description Size View
application/pdf Full Text 4.224Mb View/Open
application/pdf Cover 926.1Kb View/Open
application/pdf Title Pages_Contents 251.1Kb View/Open
application/pdf Chapter 1 277.3Kb View/Open
application/pdf Chapter 2 385.2Kb View/Open
application/pdf Part I: Chapter 3 209.9Kb View/Open
application/pdf Part I: Chapter 4 411.6Kb View/Open
application/pdf Part I: Chapter 5 304.4Kb View/Open
application/pdf Part II: Chapter 6 401.4Kb View/Open
application/pdf Part II: Chapter 7 502.8Kb View/Open
application/pdf Part II: Chapter 8 573.6Kb View/Open
application/pdf Part II: Chapter 9 711.4Kb View/Open
application/pdf Part III: Chapter 10 356.4Kb View/Open
application/pdf Part III: Chapter 11 349.5Kb View/Open
application/pdf Chapter 12 125.6Kb View/Open
application/pdf Summary in Dutch 279.9Kb View/Open
application/pdf Curriculum Vitae_Acknowledgements_Bibliography 274.9Kb View/Open
application/pdf Propositions 99.27Kb View/Open

This item appears in the following Collection(s)