## 3 The papers
### Problem area # 1 : sequence analysis  
Multiple alignment.Comparing genomic sequences drawn from individuals of the same or different species is one of the fundamental problems in molecular biology. The comparisons are aimed at identifying highly conserved (and, therefore, presumably functionally relevant) DNA regions, spot fatal mutations, suggest evolutionary relationships, or help in correcting sequencing errors. A genomic sequence can be represented as a string over an alphabet \(\Sigma\) consisting of either the 4 nucleotide letters or the 20 letters identifying the 20 aminoacids. Aligning a set of sequences (i.e., computing a _Multiple Sequence Alignment_) consists in arranging them in a matrix having each sequence in a row. This is obtained by possibly inserting gaps (represented by the '-' character) in each sequence so that they all result of the same length. The goal of identifying common patterns is pursued by attempting as much as possible to place the same character in every column. The following is a simple example of an alignment of the sequences ATTCCGAC, TTCCCTG and ATCCTC. The example highlights that the pattern TCC is common to all sequences. - T T C C C
- T G  
A - T C C - - T C  
The multiple sequence alignment problem has been formalized as an optimization problem. The most popular objective function for multiple alignment generalizes ideas from optimally aligning twosequences. This problem, called _pairwise alignment_, is formulated as follows: Given symmetric costs (or, alternatively, profits) \(\gamma(a,b)\) for replacing a letter \(a\) with a letter \(b\) and costs \(\gamma(a,-)\) for deleting or inserting a letter \(a\), find a minimum-cost (respectively, maximum-profit) set of symbol operations that turn a sequence \(S^{\prime}\) into a sequence \(S^{\prime\prime}\). For genomic sequences, the costs \(\gamma(\cdot,\cdot)\) are usually specified by some widely used _substitution matrices_ (e.g., PAM and BLOSUM), which score the likelihood of specific letter mutations, deletions and insertions. An _alignment_\(\mathcal{A}\) of two or more sequences is a bidimensional array having the (gapped) sequences as rows. The value \(d_{\mathcal{A}}(S^{\prime},S^{\prime\prime})\) of an alignment of two sequences \(S^{\prime}\) and \(S^{\prime\prime}\) is obtained by adding-up the costs for the pairs of characters in corresponding positions. The objective is generalized, for \(k\) sequences \(\{S_{1},\ldots,S_{k}\}\), by the _Sum-of-Pairs_ (SP) score, in which the cost of an alignment is obtained by adding-up the costs of the symbols matched up at the same positions, over all the pairs of sequences:  
\[SP(\mathcal{A}):=\sum_{1\leq i<j\leq k}d_{\mathcal{A}}(S_{i},S_{j})=\sum_{1 \leq i<j\leq k}\,\sum_{l=1}^{|\mathcal{A}|}\gamma(\mathcal{A}[i][l],\mathcal{ A}[j][l]) \tag{1}\]  
where \(|\mathcal{A}|\) denotes the length of the alignment, i.e., the number of its columns. Finding the optimal SP alignment was shown to be NP-hard by [PERSON] and [PERSON] [4]. A Dynamic Programming solution for the alignment of \(k\) sequences, of length \(l\), yields an exponential-time algorithm of complexity \(O(2^{k}l^{k})\). In typical real-life instances, while \(k\) can be possibly small (e.g., around 10), \(l\) is in the order of several hundreds, and the Dynamic Programming approach turns out to be infeasible for all but tiny problems. Alignment problems can be cast as special types of _non-crossing matching_ problems. Each sequence \(S_{i}\) represents the \(i\)-th level of a layered graph, with the letters of \(S_{i}\) being the nodes of the graph at level \(i\). Each pair of levels induces a complete bipartite graph. A matching between two levels specifies which characters have to be aligned to each other. The matching must be non-crossing, i.e., if the \(k\)-th letter of a sequence is matched to the \(j\)-th letter of another, no letter preceding \(k\) in the first sequence can be matched to a letter following \(j\) in the second.