## 1 Introduction
### Article Organization  
This article is organized as follows. Section 2 shows a first application example, even before the formal definitions are given. In Section 3, we collect technical definitions which are familiar from the literature. Readers with a strong background in these concepts may skip their formal exposition and jump right ahead. In Section 4, we formally introduce ICOREs. We suggest a pseudocode notation for writing ICOREs, add some notational conventions, and offer an ICORE design exercise to the reader. Then, we proceed to model various problems in biosequence and structure analysis. Section 5 discusses sequence comparison problems in various guises, Section 6 deals with folding RNA sequences into a secondary structure and related problems such as stochastic RNA family models, and Section 7 focuseson several variants of tree comparison and pattern matching. Table 1 summarizes the ICOREs presented in this manuscript. Curious readers are invited to skip all the technicalities and take a look ahead, to see how the problem they are most familiar with is dressed up as an ICORE. While Sections 5-7 are concerned with the construction of the search spaces for various problem types, Section 8 deals with the evaluation of search spaces, including the combined use of several scoring schemes and objective functions. In Section 9, we relate ICOREs to the present state-of-the-art in implementing algebraic dynamic programming, and to other computational models from older work. In the Conclusion, we review some design decisions that were made with this first exposition of ICOREs, and discuss the challenges of ICORE implementation.  
\begin{table}
\begin{tabular}{l c l c c} \hline \hline
**ICORE/Grammar** & **Dim.** & **Problem addressed** & **In Section** & **Page** \\ \hline EditDistance & 2 & simple edit distance/alignment & 4.2 & 77 \\ Affine & 2 & edit distance, affine gaps & 5.1 & 82 \\ Aff@Sci & 2 & oscillating affine gaps & 5.1 & 84 \\ Aff@Trace & 2 & sequence traces, affine gaps & 5.1 & 84 \\ LocalSearch & 2 & generic local alignment & 5.2 & 85 \\ MotifSearch & 2 & short in long alignment & 5.2.1. & 86 \\ SemiGlo@Alignment & 2 & semi-global alignment & 5.2.2. & 86 \\ Local@Alignment & 2 & local alignment & 5.2.3. & 86 \\ MatchSeq\_S & 1 & hardwired sequence matching & 5.3.1. & 88 \\ MatchAff\_S & 1 & same with affine gap model & 5.3.1. & 88 \\ MatchSeq\_S & 1 & profile HMM & 5.3.2. & 88 \\ with position-specific scores & & & & \\ \hline RNAfold & 1 & RNA folding & 6.3 & 93 \\ StructAli & 2 & struct. Alignment prototype & 6.4 & 97 \\ SimultaneousFolding & 2 & generalized fold and align & 6.5 & 98 \\ ExactConsensusStructure & 2 & exact consensus structure & 6.5.2. & 98 \\  & & for two RNA sequences & & \\ Sankoff & 2 & simultaneous fold and align & 6.5.3. & 99 \\ S2 SGeneric & 2 & covariance model, generic & 6.6.1. & 101 \\ S2 SExact & 2 & match RNA sequence & 6.6.2. & 100 \\  & & to target structure & & \\ Match\_S2S\_r & 2 & exact local motif matcher & 6.6.4. & 103 \\ Match\_S2S\_r’ & 1 & motif matcher, hard coded & 6.6.4. & 104 \\ SCFG & 1 & stochastic context free grammar & 6.3 & 93 \\ CovarianceModel\_r & 1 & covariance model, hard coded & 6.6.5. & 106 \\ \hline TreeAlign & 2 & classical tree alignment & 7.2 & 111 \\ TreeAliGeneric & 2 & tree alignment prototype + variants & 7.2.2. & 113 \\ OsciSubforest & 2 & tree ali. with oscillating gaps & 7.2.2. & 117 \\ TreeEdit & 2 & classical tree edit & 7.3 & 119 \\ RNATreeAli & 2 & RNA structure alignment & 7.5 & 127 \\ \hline \hline \end{tabular}
\end{table}
Table 1: A summary of the Inverse Coupled Rewrite Systems (ICOREs) presented in this manuscript. In a few cases, not a complete ICORE is specified, but only a grammar that extends another ICORE.