File Alignment.h

↰ Parent directory (ADS/string)

The alignments of two strings P and T of exercises 13.7-13.9: spaces are inserted in P or T, never one in front of the other, and each column scores +1 if the characters are equal, -1 if they differ and -2 if one is a space.

Definition (ADS/string/Alignment.h)

Detailed Description

DP[ i ][ j ], the best score of P( i ) and T( j ), is :math:`[
max{ DP[ i ][ j - 1 ] - 2 , DP[ i - 1 ][ j ] - 2 ,

DP[ i - 1 ][ j - 1 ] + delta_{ij} }

` with :math:` delta_{ij} = pm 1 `, Theta( m n ) time:

  • global, DP[ i ][ 0 ] = -2 i and DP[ 0 ][ j ] = -2 j, the score in DP[ m ][ n ];

  • semiglobal, the spaces before the start and after the end of either string free: the first row and column are 0, the score the largest of the last row and column;

  • local, the best alignment of two substrings: 0 is a fourth term of the maximum, and the score the largest entry.

The contracts [see File Contract.h]: the two strings of a global alignment have the same length, at least that of the longer string. The operations are defined in Alignment.tpp.

  1. Montresor, Algoritmi e Strutture Dati, 2025, exercises 13.7-13.9, https://algoritmicamente.it/materiali/libro/capitoli/cap13.pdf

    1. Needleman, C. D. Wunsch, A general method applicable to the search for similarities in the amino acid sequence of two proteins, Journal of Molecular Biology 48(3), 443-453, 1970, doi:10.1016/0022-2836(70)90057-4

    1. Smith, M. S. Waterman, Identification of common molecular subsequences, Journal of Molecular Biology 147(1), 195-197, 1981, doi:10.1016/0022-2836(81)90087-5

Donato Meoli

Dipartimento di Informatica Universita’ di Pisa

by Donato Meoli

Includes

Included By

Namespaces

Enums

Functions