DNA Expressions
A Formal Notation for DNA

DNA expressions are strings denoting certain types of DNA molecules. This page lists the publications written by Rudy van Vliet, Hendrik Jan Hoogeboom and Grzegorz Rozenberg about these expressions.

PhD thesis

On 10 December, 2015, Rudy van Vliet defended his PhD thesis (at Leiden University) entitled DNA Expressions - A Formal Notation for DNA. The final version of the thesis can be found here (as pdf). The Stellingen (propositions) belonging to the PhD thesis (only in Dutch) can be found here (as pdf). There is also a list of errata for the thesis.

Making DNA Expressions Minimal
A Minimal Normal Form for DNA Expressions

Rudy van Vliet and Hendrik Jan Hoogeboom have written two papers and submitted them together, as a diptych, for publication in the scientific journal Fundamenta Informaticae. The papers were accepted, and were published in 2013.

The first paper is entitled Making DNA Expressions Minimal. The abstract of this paper reads:

DNA expressions constitute a formal notation for DNA molecules that may contain nicks and gaps. Different DNA expressions may denote the same DNA molecule. We describe an algorithm to rewrite a given DNA expression into a DNA expression of minimal length denoting the same molecule.

The paper is available here (as pdf). You can also find the paper directly at the publisher's website, when you follow this link.

The second paper is entitled A Minimal Normal Form for DNA Expressions. The abstract of this paper reads:

DNA expressions constitute a formal notation for DNA molecules that may contain nicks and gaps. Different DNA expressions may denote the same DNA molecule. We define a (minimal) normal form for the language of DNA expressions, and describe an algorithm to rewrite a given DNA expression into the normal form.

The paper is available here (as pdf). You can also find the paper directly at the publisher's website, when you follow this link.

You may refer to the papers as
R. van Vliet, H.J. Hoogeboom: Making DNA expressions minimal, Fundamenta Informaticae, 123(2), 2013, 199-226
and R. van Vliet, H.J. Hoogeboom: A minimal normal form for DNA expressions, Fundamenta Informaticae, 123(2), 2013, 227-243,
respectively.

Technical Report 2011-03

The interested reader of the papers Making DNA Expressions Minimal and A Minimal Normal Form for DNA Expressions may wish to see more details. Therefore, we compiled the technical report All about a Minimal Normal Form for DNA Expressions. The report is registered as Technical Report 2011-03 of the Leiden Institute of Advanced Computer Science, the computer science institute of Leiden University.

You may refer to the report as R. van Vliet: All about a Minimal Normal Form for DNA Expressions, Technical Report 2011-03, Leiden Institute of Advanced Computer Science, Leiden University (2011).

The Construction of Minimal DNA Expressions

After DNA 10, the Tenth International Meeting on DNA Computing, Rudy van Vliet, Hendrik Jan Hoogeboom and Grzegorz Rozenberg were invited to write a revised and extended version of their DNA 10 paper Combinatorial Aspects of Minimal DNA Expressions. The result, entitled The Construction of Minimal DNA Expressions, has appeared in a special issue of Natural Computing - An International Journal. The abstract of the paper reads

We describe a formal language/notation for DNA molecules that may contain nicks and gaps. The elements of the language, DNA expressions, denote formal DNA molecules. Different DNA expressions may denote the same formal DNA molecule. We analyse the shortest DNA expressions denoting a given formal DNA molecule. We determine lower bounds on their lengths and explain how we construct these minimal DNA expressions.

The paper is available here (as pdf). You can also find the paper directly at the publisher's website, when you follow this link. Note that in this paper, we sometimes use terminology which is different from the one in the original DNA 10 paper and the technical report 2004-03 below.

You may refer to the paper as
R. van Vliet, H.J. Hoogeboom, G. Rozenberg: The construction of minimal DNA expressions, Natural Computing, 5(2), May 2006, 127-149.

Combinatorial Aspects of Minimal DNA Expressions

From June 7 till June 10, 2004, DNA 10, the Tenth International Meeting on DNA Computing, was held at the University of Milano-Bicocca, Italy. Rudy van Vliet, Hendrik Jan Hoogeboom and Grzegorz Rozenberg had submitted a paper entitled Combinatorial Aspects of Minimal DNA Expressions as full paper to this conference. The paper was accepted for oral presentation, and it was awarded one of two best student paper awards. The final version of the paper has been included in the conference proceedings, which has appeared as volume 3384 of Lecture Notes in Computer Science (LNCS). The abstract of the paper reads

We describe a formal language/notation for DNA molecules that may contain nicks and gaps. The elements of the language, DNA expressions, denote formal DNA molecules. Different DNA expressions may denote the same formal DNA molecule. We analyse the shortest DNA expressions denoting a given formal DNA molecule: what is their length, how are they constructed, how many of them are there, and how can they be characterized.

The paper is available here (as pdf). You can also find the paper directly at the publisher's website, when you follow this link.

You may refer to the paper as
R. van Vliet, H.J. Hoogeboom, G. Rozenberg: Combinatorial aspects of minimal DNA expressions, DNA Computing -- 10th International Workshop on DNA Computing, DNA10, Milan, Italy, June 7-10, 2004 -- Revised Selected Papers, Lecture Notes in Computer Science 3384 (C. Ferretti, G. Mauri, C. Zandron, eds.), Springer-Verlag, Berlin (2005), 375-388.

Presentation

The paper has been presented at DNA 10 by Rudy van Vliet on Tuesday, June 8, 2004. The presentation (made with Microsoft Powerpoint 97 SR-2) is available here.

Technical Report 2004-03

Due to space limitations, we could not include the formal proofs of the results in the DNA 10 paper Combinatorial Aspects of Minimal DNA Expressions. Although the Natural Computing paper The Construction of Minimal DNA Expressions does contain some sketches of proofs, the formal details have been omitted. The complete proofs can be found in the technical report Combinatorial Aspects of Minimal DNA Expressions (ext.). As the title suggests, this report can be considered as an extended version of the DNA 10 paper. The report is registered as Technical Report 2004-03 of the Leiden Institute of Advanced Computer Science, the computer science institute of Leiden University.

There are two differences between the first version of the technical report and the final version. On 2 April, 2004, one reference has been removed from the list of references. It was not referred to anyway. On 20 July, 2011, the proof of a certain property has been removed. The report also contained (and still contains) another proof of the same property.

You may refer to the report as R. van Vliet: Combinatorial Aspects of Minimal DNA Expressions (ext.), Technical Report 2004-03, Leiden Institute of Advanced Computer Science, Leiden University (2004).

Questions and comments can be sent to Rudy van Vliet: rvvliet@liacs.nl.

Last modified: 11 December, 2015 - http://www.liacs.leidenuniv.nl/~vlietrvan1/dnaexpressions/