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