DNA Expressions - a Formal Notation for DNA Molecules

A Minimal Normal Form for DNA Expressions

On 26 July, 2011, Rudy van Vliet and Hendrik Jan Hoogeboom submitted a paper entitled A Minimal Normal Form for DNA Expressions to a scientific journal. The abstract of this paper reads:

DNA expressions consitute a formal language/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 this language and describe an algorithm to rewrite a given DNA expression into the normal form.

The paper is available here (as pdf). Of course, if the paper gets accepted, then it will be revised in accordance with the referees' comments. Hence, the above PDF is probably not the final version.

Technical Report 2011-03

Due to space limitations, we could only include sketches of the proofs of the results in the paper A Minimal Normal Form for DNA Expressions. The complete proofs can be found in 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: July 26, 2011 - http://www.liacs.nl/home/rvvliet/dnaexpressions/index.html