Home Home Uni Bielefeld BiBiServ Practical Computer Science Technische Fakultaet Home Applications Education Advanced Compiler HMM Literature Team
Kopfgrafik
Navigation

Global similarity with affine gap scores (sequence alignment)

Read the full description in Towards a discipline of dynamic programming.

Sequence 1: Sequence 2:

Input:

Algebra: ***            Algebra explanation

Grammar:   affineglobsim

Output:


For usage on your local machine:


ADP Source Code

> module AffineGlobSim where

> import Data.Array
> import ADPCombinators
> import Data.List


The signature: Open source code in new window
> data Alignment = Nil Char               |
>                  D  Char Alignment      |
>                  I  Alignment Char      |
>                  R  Char Alignment Char |
>                  Dx Char Alignment      |
>                  Ix Alignment Char
>                                         deriving (Eq, Show)


Algebra type: Open source code in new window
> type AffineGlobsim_Algebra alphabet answer = (
>   alphabet -> answer,                       -- nil
>   alphabet -> answer -> answer,             -- d
>   answer -> alphabet -> answer,             -- i
>   alphabet -> answer -> alphabet -> answer, -- r
>   alphabet -> answer -> answer,             -- dx
>   answer -> alphabet -> answer,             -- ix
>   [answer] -> [answer]                      -- h
>   )



Enumeration algebra: Open source code in new window
> enum :: AffineGlobsim_Algebra Char Alignment
> enum = (nil, d, i, r, dx, ix, h) where
>    nil = Nil
>    d   = D
>    i   = I
>    r   = R
>    dx  = Dx
>    ix  = Ix
>    h   = id
> 


Pretty printing algebra: Open source code in new window
> prettyprint :: AffineGlobsim_Algebra Char (String, String)
> prettyprint = (nil, d, i, r, dx, ix, h) where
>   nil _        = ("","")
>   d  x (l,r)   = (x:l, open:r)
>   i    (l,r) y = (open:l, y:r)
>   r  x (l,r) y = (x:l,y:r)
>   dx x (l,r) 	 = (x:l, extend:r)
>   ix   (l,r) y = (extend:l, y:r)
>   h            = id
>   open         = '='
>   extend	 = '-'


Counting algebra: Open source code in new window
> count :: AffineGlobsim_Algebra Char Int
> count = (nil, d, i, r, dx, ix, h) where
>    nil a   = 1
>    d x s   = s
>    i s y   = s
>    r a s b = s
>    dx x s  = s
>    ix s y  = s
>    h []    = []
>    h l     = [sum l]


Affine gap score algebra: Open source code in new window
> affine :: AffineGlobsim_Algebra Char Int
> affine = (nil, d, i, r, dx, ix, h) where
>  nil a   = 0
>  d x s   = s + open + extend
>  i s y   = s + open + extend
>  r a s b = s + w a b
>  dx x s  = s + extend
>  ix s y  = s + extend
>  h []    = []
>  h l     = [maximum l]
>
>  -- simple definitions for open, extend and w:
>  open   = (-15)
>  extend = (-1)
>  w a b  = if a==b then 4 else -3



Algebra product operation: Open source code in new window
> infix ***
> (***) :: Eq answer1 =>
>          AffineGlobsim_Algebra alphabet answer1 ->
>          AffineGlobsim_Algebra alphabet answer2 ->
>          AffineGlobsim_Algebra alphabet (answer1, answer2)
> alg1 *** alg2 = (nil, d, i, r, dx, ix, h) where
>    (nil1, d1, i1, r1, dx1, ix1, h1) = alg1
>    (nil2, d2, i2, r2, dx2, ix2, h2) = alg2
> 
>    nil a = (nil1 a, nil2 a)
>    d  x (s1,s2)   = (d1 x s1, d2 x s2)
>    i    (s1,s2) y = (i1 s1 y, i2 s2 y)
>    r  x (s1,s2) y = (r1 x s1 y, r2 x s2 y)
>    dx x (s1,s2)   = (dx1 x s1, dx2 x s2)
>    ix   (s1,s2) y = (ix1 s1 y, ix2 s2 y)
> 
>    h xs = [(x1,x2)| x1 <- nub $ h1 [ y1 | (y1,y2) <- xs],
>                     x2 <-       h2 [ y2 | (y1,y2) <- xs, y1 == x1]]


The yield grammar: Open source code in new window
> affineglobsim alg f = axiom alignment where
>   (nil, d, i, r, dx, ix, h) = alg

>   alignment = tabulated (
>                nil <<< char '$'                       |||
>                d   <<< achar  -~~ xDel                |||
>                i   <<<            xIns      ~~- achar |||
>                r   <<< achar  -~~ alignment ~~- achar ... h)

>   xDel      = tabulated (
>                alignment              |||
>                dx <<< achar  -~~ xDel ... h )

>   xIns      = tabulated (
>                alignment             |||
>                ix <<< xIns ~~- achar ... h )


Bind input:
>   z         = mk f
>   (_,n)     = bounds z
>   achar     = acharSep' z '$'
>   char      = char' z
>   tabulated = table n
>   axiom     = axiom' n



| Author: mruether | Date: 2004/10/01 15:52:12 |