Practical Computer Science - Bielefeld University

Pattern matching on trees and tree comparison are classical topics in computer science. It is used, for example, in comparing structured documents, structured physical objects assembled in a tree like fashion, or molecular structures that can be represented as trees. Term rewrite systems require to match rewrite rules to target terms, and compiler code generation involves matching patterns that describe machine instructions to intermediate program code.
In bioinformatics, there is a large demand on tree comparison methods for modeling RNA secondary structure and finding novel RNA genes via structural matching.
In the seminar, we shall focus on the algorithmic aspects of tree pattern matching. We shall review some of the classical algorithms, and study some very recent enhancements.

literatur
(1) Classical Articles

K.-C. Tai. The tree-to-tree correction problem. Journal of the ACM, 26(3):422-433, 1979
B.A. Shapiro and K.Z. Zhang. Comparing multiple RNA secondary structures using tree comparisons. Computer Applications in Bioscience, 6(4):309-318, Oct, 1990
T. Jiang, L. Wang, and K. Zhang. Alignment of trees - an alternative to tree edit. Theoretical Computer Science, 143(1):137-148, 1995

(2) Applications in RNA structure comparison

M. Hoechsmann, B. Voss, and R. Giegerich. Pure multiple RNA secondary structure alignments: A progressive profile approach. IEEE/ACM Transactions on Computational Biology and Bioinformatics, 1:53-62, 2004
S. Schirmer, R.Giegerich. Forest alignment with affine gaps and anchors. Submitted to TCS, 2011
Guillaume Blin, Alain Denise, Serge Dulucq, Claire Herrbach, and Helene Touzet. Alignments of RNA Structures. IEEE/ACM Transactions on Computational Biology and Bioinformatics, Vol. 7, No. 2, April-June, 2010

(3) Recent applications to XML document processing

Peter L. Thomas, David F. Brailsford. Enhancing Composite Digital Documents Using XML-based Standoff Markup. Proceedings Document Engineering, 2005
Sebastian Roennau, Geraint Philipp, Uwe M. Borghoff. Efficient Change Control of XML Documents. Proceedings Document Engineering, 2009
Davi de Castro Reis, Paulo B. Golgher, Altigran S. da Silva, Alberto H. F. Laender. Automatic Web News Extraction Using Tree Edit Distance. WWW2004, May 17--22, 2005, New York, New York, USA. ACM158113844X/04/0005