Teaching > FiniteStateMachines

# Finite-state machines for sequence analysis

## Pattern-matching

### MCB binding site

digraph G {

START [shape=octagon, color=black]; END [shape=octagon, color=black];

L [shape=square, label="(any base)"]; R [shape=square, label="(any base)"];

P1 [shape=square, label=A]; P2 [shape=square, label=C]; P3 [shape=square, label=G]; P4 [shape=square, label=C]; P5 [shape=square, label=G]; P6 [shape=square, label=T];

START -> L -> L -> P1 -> P2 -> P3 -> P4 -> P5 -> P6 -> R -> R -> END; START -> P1; P6 -> END;

label="Finite-state machine for matching MCB binding site"; }

## Pairwise alignment

### Needleman-Wunsch

digraph G {

START [shape=octagon, color=black]; END [shape=octagon, color=black];

S [shape=square, color=red];

I [shape=circle, color=black, label=<

 - Y
>]; D [shape=circle, color=black, label=<
 X -
>]; M [shape=circle, color=black, label=<
 X Y
>];

START->S->END;

S->I [label=G]; I->S;

S->D [label=G]; D->S;

S->M [label="Q(X,Y)"]; M->S;

label="Finite-state machine for Needleman-Wunsch alignment"; }

### Smith-Waterman

digraph G {

START [shape=octagon, color=black]; END [shape=octagon, color=black];

S [shape=square, color=red];

L [shape=circle, color=black]; IL [shape=circle, color=black, label=<

 - Y
>]; DL [shape=circle, color=black, label=<
 X -
>];

R [shape=circle, color=black]; IR [shape=circle, color=black, label=<

 - Y
>]; DR [shape=circle, color=black, label=<
 X -
>];

I [shape=circle, color=black, label=<

 - Y
>]; D [shape=circle, color=black, label=<
 X -
>]; M [shape=circle, color=black, label=<
 X Y
>];

START->L->S->R->END;

S->I [label=G]; I->S;

S->D [label=G]; D->S;

S->M [label="Q(X,Y)"]; M->S;

L->IL->L->DL->L; R->IR->R->DR->R;

label="Finite-state machine for Smith-Waterman alignment"; }

### Gotoh

digraph G {

START [shape=octagon, color=black]; END [shape=octagon, color=black];

S [shape=square, color=red]; T [shape=square, color=red];

L [shape=circle, color=black]; IL [shape=circle, color=black, label=<

 - Y
>]; DL [shape=circle, color=black, label=<
 X -
>];

R [shape=circle, color=black]; IR [shape=circle, color=black, label=<

 - Y
>]; DR [shape=circle, color=black, label=<
 X -
>];

I [shape=circle, color=black, label=<

 - Y
>]; D [shape=circle, color=black, label=<
 X -
>]; M [shape=circle, color=black, label=<
 X Y
>];

START->L->S->R->END;

S->I [label=G]; T->I [label=E];

S->D [label=G]; T->D [label=E];

S->M [label="Q(X,Y)"]; T->M [label="Q(X,Y)"];

I->T; D->T; M->S;

L->IL->L->DL->L; R->IR->R->DR->R;

label="Finite-state machine for Gotoh alignment"; }

-- IanHolmes - 21 Nov 2007

Copyright © 2008-2014 by the contributing authors. All material on this collaboration platform is the property of the contributing authors.
Ideas, requests, problems regarding TWiki? Send feedback