Definition

Definition 12     Sei $\Sigma$ ein endliches Alphabet ohne das Leerzeichen '-' und $\Sigma'=\Sigma\cup \{'-'\}$. Seien weiter $S_1,\ldots,S_k$ k Sequenzen über $\Sigma$ mit Längen $n_1,\ldots,n_k$. Ein (globales) multiples Alignment A von $S_1,\ldots,S_k$ ist eine Matrix der Dimension $k\times l$ mit den folgenden Eigenschaften:

• $\max\{n_1,\ldots,n_k\} \leq l \leq \sum_{i=1}^k n_i$.
• $A[i][j] \in \Sigma' \quad \forall \ 1\leq i \leq k, 1\leq j\leq l$.
• Die i-te Reihe ergibt ohne Leerzeichen String S_i.
• Es gibt keine Spalte, die nur aus Leerzeichen besteht.

Beispiel 8    

         S1 = - G C T G A T A T A G C T
         S2 = G G G T G A T - T A G C T
         S3 = - G C T - A T - - C G C -
         S4 = A G C G G A - A C A C C T

In der Folge werden wir von (multiplen) Alignments von Untermengen der k Strings reden. Dazu führen wir noch folgende Notation ein.

Definition 13   Sei A eine multiples Alignment für die k Strings $S_1,\ldots,S_k$ und $I\subseteq \{1,\ldots,k\}$ eine Menge von Indizes, welche eine Untermenge der k Strings definiert. Sei A_I das Alignment, welches man erhält, indem man alle Reihen $i\in I$ aus A nimmt und dann alle Spalten löscht, welche nur aus Leerzeichen bestehen. Dann nennt man A_I die Projektion von A auf I. Wenn die Menge I explizit angegeben wird, vereinfachen wir die Notation und schreiben statt $A_{\{i,j,k\}}$ vereinfacht A_i,j,k

Beispiel 9    

         S1 = - G C T G A T A T A G C T
         S2 = G G G T G A T - T A G C T
         S3 = - G C T - A T - - C G C -
         S4 = A G C G G A - A C A C C T

Die Projektion A_2,3 erhält man, indem man die zweite und dritte Reihe des Alignments nimmt:

         S2 = G G G T G A T - T A G C T
         S3 = - G C T - A T - - C G C -

und dann die Spalte, welche nur aus Leerzeichen besteht löscht:

         S2 = G G G T G A T T A G C T
         S3 = - G C T - A T - C G C -