AlignmentAlgorithms 0.0.2.1 → 0.1.0.0

raw patch · 11 files changed

+527/−88 lines, 11 filesdep ~ADPfusiondep ~FormalGrammarsdep ~PrimitiveArrayPVP ok

version bump matches the API change (PVP)

Dependency ranges changed: ADPfusion, FormalGrammars, PrimitiveArray, base, containers, fmlist, vector

API changes (from Hackage documentation)

Files

• AlignmentAlgorithms.cabal +45/−15
• DP/Alignment/Global/Tapes2.hs +0/−73
• DP/HMM/States2.hs +27/−0
• DP/Seq/Align/Global/Affine2.hs +82/−0
• DP/Seq/Align/Global/Linear2.hs +73/−0
• DP/Seq/Align/SemiGlobal/Infix2.hs +103/−0
• DP/Tree/Align/Global/Affine2.hs +64/−0
• DP/Tree/Align/Global/AffineSmall2.hs +57/−0
• DP/Tree/Align/Global/Linear2.hs +40/−0
• DP/Tree/Edit/Global/Linear2.hs +31/−0
• changelog.md +5/−0

@@ -1,7 +1,7 @@ name:           AlignmentAlgorithms-version:        0.0.2.1-author:         Christian Hoener zu Siederdissen, 2013-2015-copyright:      Christian Hoener zu Siederdissen, 2013-2015+version:        0.1.0.0+author:         Christian Hoener zu Siederdissen, 2013-2017+copyright:      Christian Hoener zu Siederdissen, 2013-2017 homepage:       https://github.com/choener/AlignmentAlgorithms bug-reports:    https://github.com/choener/AlignmentAlgorithms/issues maintainer:     choener@bioinf.uni-leipzig.de@@ -11,7 +11,7 @@ build-type:     Simple stability:      experimental cabal-version:  >= 1.10.0-tested-with:    GHC == 7.8.4, GHC == 7.10.2+tested-with:    GHC == 7.10.3, GHC == 8.0.1 synopsis:       Collection of alignment algorithms description:                 <http://www.bioinf.uni-leipzig.de/Software/gADP/ generalized Algebraic Dynamic Programming>@@ -25,10 +25,32 @@                 That being said, these algorithms are mostly aimed towards                 sequence alignment problems.                 .-                List of grammars:+                List of grammars for sequences:                 .-                * global alignment (Needleman-Wunsch style)+                * global alignment+                  * linear scoring: Needleman-Wunsch style+                  .+                  * affine scoring: Gotoh                 .+                * semiglobal alignment+                  * overhang alignment+                .+                List of grammar for trees:+                .+                * global alignment+                  * linear scoring+                  .+                  * affine scoring+                  .+                  * simplified affine scoring+                .+                * global editing+                  * linear scoring+                .+                We now provide tree alignment and editing algorithms as well.+                We do not depend on ADPfusionForest to achieve this because+                grammar rules are completely disconnected from the underlying+                ADPfusion machinery.   @@ -39,16 +61,24 @@   library-  build-depends: base             >= 4.7      && < 4.9-               , ADPfusion        >= 0.4.0.2  && < 0.5.1-               , containers       >= 0.5      && < 0.6-               , fmlist           >= 0.9      && < 0.10-               , FormalGrammars   >= 0.2.1    && < 0.2.2-               , GrammarProducts  >= 0.1.1    && < 0.1.2-               , PrimitiveArray   >= 0.6.0    && < 0.7.1-               , vector           >= 0.10     && < 0.12+  build-depends: base             >= 4.7      && < 5.0+               , containers       >= 0.5+               , fmlist           >= 0.9+               , vector           >= 0.10+               --+               , ADPfusion        == 0.5.2.*+               , FormalGrammars   == 0.3.1.*+               , GrammarProducts  == 0.1.1.*+               , PrimitiveArray   == 0.8.0.*   exposed-modules:-    DP.Alignment.Global.Tapes2+    DP.HMM.States2+    DP.Seq.Align.Global.Affine2+    DP.Seq.Align.Global.Linear2+    DP.Seq.Align.SemiGlobal.Infix2+    DP.Tree.Align.Global.Affine2+    DP.Tree.Align.Global.AffineSmall2+    DP.Tree.Align.Global.Linear2+    DP.Tree.Edit.Global.Linear2   default-language:     Haskell2010   default-extensions: BangPatterns

@@ -1,73 +0,0 @@---- | Very simple pairwise global alignment. The terminal tapes may contain--- the atomic types @u@ and @l@ which means that one may align sequences of--- different types.------ In case you want to align nucleotides to amino acids, this version--- should only be used if the nucleotides are already in triplet form and--- have no frameshift within the sequence. Alternatively, specify a derived--- grammar of higher complexity.--module DP.Alignment.Global.Tapes2 where--import           Data.Sequence (Seq,empty,(|>))-import           Data.Vector.Fusion.Stream.Monadic (Stream,toList)-import qualified Data.FMList as F-import           Data.FMList (FMList)--import ADP.Fusion-import Data.PrimitiveArray hiding (toList)-import FormalLanguage------ | Define signature and grammar--[formalLanguage|-Grammar: Global-N: X-T: l-T: u-S: [X,X]-[X,X] -> done  <<< [e,e]-[X,X] -> align <<< [X,X] [l,u]-[X,X] -> indel <<< [X,X] [-,u]-[X,X] -> delin <<< [X,X] [l,-]-//--Emit: Global-|]--makeAlgebraProduct ''SigGlobal---- | Generic backtracking scheme via @FMList@s.--backtrack :: Monad m => u -> l -> SigGlobal m (FMList (l,u)) [FMList (l,u)] l u-backtrack ud ld = SigGlobal-  { done  = \ _ -> F.empty-  , align = \ x (Z:.l:.u) -> x `F.snoc` (l ,u )-  , indel = \ x (Z:._:.u) -> x `F.snoc` (ld,u )-  , delin = \ x (Z:.l:._) -> x `F.snoc` (l ,ud)-  , h     = toList-  }-{-# Inline backtrack #-}---- | Backtracking with more options--backtrackFun :: Monad m => (l -> u -> r) -> (l -> u -> r) -> u -> l -> SigGlobal m (FMList r) [FMList r] l u-backtrackFun f g ud ld = SigGlobal-  { done  = \ _ -> F.empty-  , align = \ x (Z:.l:.u) -> x `F.snoc` f l  u-  , indel = \ x (Z:._:.u) -> x `F.snoc` g ld u-  , delin = \ x (Z:.l:._) -> x `F.snoc` g l  ud-  , h     = toList-  }-{-# Inline backtrackFun #-}---- | Turn a single @FMList@ backtracking result into the corresponding--- list.--runBacktrack :: FMList r -> [r]-runBacktrack = F.toList-{-# Inline runBacktrack #-}-

@@ -0,0 +1,27 @@++module DP.HMM.States2 where++import           ADP.Fusion.Core+import           Data.PrimitiveArray hiding (toList)+import           FormalLanguage++++[formalLanguage|+Verbose+Grammar: HMM+N: P  -- plus case+N: M  -- minus case+T: x+S: M  -- we should start and stop here+P -> pstay <<< P x+P -> mtop  <<< M x+M -> mstay <<< M x+M -> ptom  <<< P x+M -> done  <<< e+//+Emit: HMM+|]++makeAlgebraProduct ''SigHMM+

@@ -0,0 +1,82 @@++module DP.Seq.Align.Global.Affine2 where++import           Data.FMList (FMList)+import           Data.Sequence (Seq,empty,(|>))+import           Data.Vector.Fusion.Stream.Monadic (Stream,toList)+import qualified Data.FMList as F++import           ADP.Fusion.Core+import           Data.PrimitiveArray hiding (toList)+import           FormalLanguage++++-- | Define signature and grammar++[formalLanguage|+Verbose+Grammar: Gotoh+N: S+N: M+N: D+N: I+T: b+T: u+S: [S,S]+[S,S] -> start <<< [M,M]+[S,S] -> start <<< [D,D]+[S,S] -> start <<< [I,I]++[M,M] -> done  <<< [e,e]+[M,M] -> align <<< [M,M] [b,u]+[M,M] -> align <<< [D,D] [b,u]+[M,M] -> align <<< [I,I] [b,u]++[D,D] -> openU <<< [M,M] [-,u]+[D,D] -> contU <<< [D,D] [-,u]+[D,D] -> openU <<< [I,I] [-,u]++[I,I] -> openL <<< [M,M] [b,-]+[I,I] -> openL <<< [D,D] [b,-]+[I,I] -> contU <<< [I,I] [b,-]+//++Emit: Gotoh+|]++makeAlgebraProduct ''SigGotoh++{-+-- | Generic backtracking scheme via @FMList@s.++backtrack :: Monad m => u -> l -> SigGlobal m (FMList (l,u)) [FMList (l,u)] l u+backtrack ud ld = SigGlobal+  { done  = \ _ -> F.empty+  , align = \ x (Z:.l:.u) -> x `F.snoc` (l ,u )+  , indel = \ x (Z:._:.u) -> x `F.snoc` (ld,u )+  , delin = \ x (Z:.l:._) -> x `F.snoc` (l ,ud)+  , h     = toList+  }+{-# Inline backtrack #-}++-- | Backtracking with more options++backtrackFun :: Monad m => (l -> u -> r) -> (l -> u -> r) -> u -> l -> SigGlobal m (FMList r) [FMList r] l u+backtrackFun f g ud ld = SigGlobal+  { done  = \ _ -> F.empty+  , align = \ x (Z:.l:.u) -> x `F.snoc` f l  u+  , indel = \ x (Z:._:.u) -> x `F.snoc` g ld u+  , delin = \ x (Z:.l:._) -> x `F.snoc` g l  ud+  , h     = toList+  }+{-# Inline backtrackFun #-}++-- | Turn a single @FMList@ backtracking result into the corresponding+-- list.++runBacktrack :: FMList r -> [r]+runBacktrack = F.toList+{-# Inline runBacktrack #-}+-}+

@@ -0,0 +1,73 @@++-- | Very simple pairwise global alignment. The terminal tapes may contain+-- the atomic types @u@ and @l@ which means that one may align sequences of+-- different types.+--+-- In case you want to align nucleotides to amino acids, this version+-- should only be used if the nucleotides are already in triplet form and+-- have no frameshift within the sequence. Alternatively, specify a derived+-- grammar of higher complexity.++module DP.Seq.Align.Global.Linear2 where++import           Data.FMList (FMList)+import           Data.Sequence (Seq,empty,(|>))+import           Data.Vector.Fusion.Stream.Monadic (Stream,toList)+import qualified Data.FMList as F++import           ADP.Fusion.Core+import           Data.PrimitiveArray hiding (toList)+import           FormalLanguage++++-- | Define signature and grammar++[formalLanguage|+Grammar: Global+N: X+T: l+T: u+S: [X,X]+[X,X] -> done  <<< [e,e]+[X,X] -> align <<< [X,X] [l,u]+[X,X] -> indel <<< [X,X] [-,u]+[X,X] -> delin <<< [X,X] [l,-]+//++Emit: Global+|]++makeAlgebraProduct ''SigGlobal++-- | Generic backtracking scheme via @FMList@s.++backtrack :: Monad m => u -> l -> SigGlobal m (FMList (l,u)) [FMList (l,u)] l u+backtrack ud ld = SigGlobal+  { done  = \ _ -> F.empty+  , align = \ x (Z:.l:.u) -> x `F.snoc` (l ,u )+  , indel = \ x (Z:._:.u) -> x `F.snoc` (ld,u )+  , delin = \ x (Z:.l:._) -> x `F.snoc` (l ,ud)+  , h     = toList+  }+{-# Inline backtrack #-}++-- | Backtracking with more options++backtrackFun :: Monad m => (l -> u -> r) -> (l -> u -> r) -> u -> l -> SigGlobal m (FMList r) [FMList r] l u+backtrackFun f g ud ld = SigGlobal+  { done  = \ _ -> F.empty+  , align = \ x (Z:.l:.u) -> x `F.snoc` f l  u+  , indel = \ x (Z:._:.u) -> x `F.snoc` g ld u+  , delin = \ x (Z:.l:._) -> x `F.snoc` g l  ud+  , h     = toList+  }+{-# Inline backtrackFun #-}++-- | Turn a single @FMList@ backtracking result into the corresponding+-- list.++runBacktrack :: FMList r -> [r]+runBacktrack = F.toList+{-# Inline runBacktrack #-}+

@@ -0,0 +1,103 @@++-- | Affine grammar with zero-cost prefixes and suffixes.++module DP.Seq.Align.SemiGlobal.Infix2 where++import           Data.FMList (FMList)+import           Data.Sequence (Seq,empty,(|>))+import           Data.Vector.Fusion.Stream.Monadic (Stream,toList)+import qualified Data.FMList as F++import           ADP.Fusion.Core+import           Data.PrimitiveArray hiding (toList)+import           FormalLanguage+import           FormalLanguage.GrammarProduct++++-- | Define signature and grammar++[grammarProduct|+Verbose++Grammar: Infix+N: S+N: P+N: U+N: M+N: D+N: I+N: S+T: b+T: u+S: S++-- consume prefix on upper tape++[P,U] -> done  <<< [e,e]+[P,U] -> prePU <<< [P,U] [-,u]++-- consume prefix on lower tape++[U,P] -> done  <<< [e,e]+[U,P] -> preUP <<< [U,P] [b,-]++-- normal affine grammar (but with additional options to transition to+-- prefix++[M,M] -> done  <<< [e,e]+[M,M] -> align <<< [M,M] [b,u]+[M,M] -> align <<< [D,D] [b,u]+[M,M] -> align <<< [I,I] [b,u]+-- this is actually right, since [P,U] and [U,P] can be empty. In order to+-- guarantee that the prefix is non-empty, we make sure here that at least+-- one character is in the respective prefix.+[M,M] -> toPUM <<< [P,U] [-,u]+[M,M] -> toUPM <<< [U,P] [b,-]++-- affine deletions.++[D,D] -> openU <<< [M,M] [-,u]+[D,D] -> contU <<< [D,D] [-,u]+[D,D] -> openU <<< [I,I] [-,u]+[D,D] -> done  <<< [e,e]+-- coming from a prefix+[D,D] -> toPUD <<< [P,U] [-,u]+[D,D] -> toUPD <<< [U,P] [b,-]++[I,I] -> openL <<< [M,M] [b,-]+[I,I] -> openL <<< [D,D] [b,-]+[I,I] -> contL <<< [I,I] [b,-]+[I,I] -> done  <<< [e,e]+-- coming from a prefix+[I,I] -> toPUI <<< [P,U] [-,u]+[I,I] -> toUPI <<< [U,P] [b,-]++-- consume suffix on upper tape++[S,U] -> frSUM <<< [M,M] [-,u]+[S,U] -> frSUD <<< [D,D] [-,u]+[S,U] -> frSUI <<< [I,I] [-,u]+[S,U] -> sufSU <<< [S,U] [-,u]++[U,S] -> frUSM <<< [M,M] [b,-]+[U,S] -> frUSD <<< [D,D] [b,-]+[U,S] -> frUSI <<< [I,I] [b,-]+[U,S] -> sufUS <<< [U,S] [b,-]++-- we can go directly to the affine part, or start in a suffix system. No+-- extra costs here, because we already pay in @frSUM@ etc++[S,S] -> start <<< [M,M]+[S,S] -> start <<< [D,D]+[S,S] -> start <<< [I,I]+[S,S] -> start <<< [S,U]+[S,S] -> start <<< [U,S]++//++Emit: Infix+|]++makeAlgebraProduct ''SigInfix+

@@ -0,0 +1,64 @@++-- | Full-blown affine-scoring tree alignment grammar with all cases.+--+-- We currently do not produce the outside algorithm, since the+-- @AffineSmall2@ variant seems more useful in practice. However, if you+-- want just send a mail.++module DP.Tree.Align.Global.Affine2 where++import ADP.Fusion.Core+import FormalLanguage.CFG++++[formalLanguage|+Verbose++Grammar: Global+N: T -- tree+N: F -- forest+N: Z -- tree for gaps+N: Y -- tree for affine gaps+N: P -- parent gap mode+N: G -- sibling gap together with P+T: n+S: [F,F]+[F,F] -> iter    <<< [T,T] [F,F]+[F,F] -> iter    <<< [T,Z] [F,G]+[F,F] -> iter    <<< [Z,T] [G,F]+[F,F] -> done    <<< [e,e]+[P,F] -> pfalign <<< [T,T] [P,F]+[P,F] -> pfdelin <<< [T,Z] [P,G]+[P,F] -> pfindel <<< [Y,T] [P,F]+[P,F] -> done    <<< [e,e]+[F,P] -> done    <<< [e,e]+[F,P] -> fpalign <<< [T,T] [F,P]+[F,P] -> fpdelin <<< [T,Y] [F,P]+[F,P] -> fpindel <<< [Z,T] [G,P]+[G,F] -> gfalign <<< [T,T] [G,F]+[G,F] -> gfdelin <<< [T,Z] [P,G]+[G,F] -> gfindel <<< [Y,T] [G,F]+[G,F] -> done    <<< [e,e]+[F,G] -> done    <<< [e,e]+[F,G] -> fgalign <<< [T,T] [F,F]+[F,G] -> fgdelin <<< [T,Y] [F,G]+[F,G] -> fgindel <<< [Z,T] [G,P]+[G,P] -> gpalign <<< [T,T] [F,P]+[G,P] -> gpdelin <<< [T,Y] [F,P]+[G,P] -> gpindel <<< [Y,T] [G,P]+[P,G] -> pgalign <<< [T,T] [P,F]+[P,G] -> pgdelin <<< [T,Y] [P,G]+[P,G] -> pgindel <<< [Y,T] [P,F]+[T,T] -> align   <<< [n,n] [F,F]+[Z,T] -> indel   <<< [-,n] [P,F]+[T,Z] -> delin   <<< [n,-] [F,P]+[Y,T] -> afindel <<< [-,n] [P,F]+[T,Y] -> afdelin <<< [n,-] [F,P]+//++Emit: Global+|]++makeAlgebraProduct ''SigGlobal+

@@ -0,0 +1,57 @@++-- | An affine-scoring grammar for the alignment of two trees.+--+-- Due to the way @ADPfusion@ and @GADP@ works this grammar will, in+-- principle, work with basically any input type. In practice, the given+-- rules make most (or only) sense for tree alignments.++module DP.Tree.Align.Global.AffineSmall2 where++import ADP.Fusion.Core+import FormalLanguage.CFG++++[formalLanguage|+Verbose++Grammar: Global+N: T -- tree+N: F -- forest+N: Z -- tree for gaps+N: Q -- sibling gap mode+N: R -- parent gap mode+N: E+T: n+S: [F,F]+[F,F] -> iter    <<< [T,T] [F,F]+[F,F] -> fgap    <<< [T,Z] [Q,Q]+[F,F] -> fgap    <<< [Z,T] [Q,Q]+[Z,T] -> indel   <<< [-,n] [R,R]+[T,Z] -> delin   <<< [n,-] [R,R]+[T,T] -> align   <<< [n,n] [F,F]+[F,F] -> done    <<< [E,E]+[R,R] -> done    <<< [E,E]+[R,R] -> pgap <<< [T,T] [R,R]+[R,R] -> pgap <<< [T,Z] [R,R]+[R,R] -> pgap <<< [Z,T] [R,R]+[Q,Q] -> done    <<< [E,E]+[Q,Q] -> siter <<< [T,T] [F,F]+[Q,Q] -> sgap <<< [T,Z] [Q,Q]+[Q,Q] -> sgap <<< [Z,T] [Q,Q]+[E,E] -> finalDone <<< [e,e]+//+Outside: Labolg+Source: Global+//++Emit: Global+Emit: Labolg+|]++makeAlgebraProduct ''SigGlobal++resig :: Monad m => SigGlobal m a b c d -> SigLabolg m a b c d+resig (SigGlobal gdo git gsi gal gin gde gfg gpg gsg gfi gh) = SigLabolg gdo git gsi gal gin gde gfg gpg gsg gfi gh+{-# Inline resig #-}+

@@ -0,0 +1,40 @@++-- | Simple, linear scoring for tree alignments.++module DP.Tree.Align.Global.Linear2 where++import ADP.Fusion.Core+import FormalLanguage.CFG++++[formalLanguage|+Verbose++Grammar: Global+N: T+N: F+N: M+T: n+S: [F,F]+[F,F] -> iter  <<< [T,T] [F,F]+[F,F] -> iter  <<< [M,M] [F,F]+[T,T] -> indel <<< [-,n] [F,F]+[T,T] -> delin <<< [n,-] [F,F]+[M,M] -> align <<< [n,n] [F,F]+[F,F] -> done  <<< [e,e]+//+Outside: Labolg+Source: Global+//++Emit: Global+Emit: Labolg+|]++makeAlgebraProduct ''SigGlobal++resig :: Monad m => SigGlobal m a b c d -> SigLabolg m a b c d+resig (SigGlobal gdo git gal gin gde gh) = SigLabolg gdo git gal gin gde gh+{-# Inline resig #-}+

@@ -0,0 +1,31 @@++-- | Simple, linear tree editing grammar.++module DP.Tree.Edit.Global.Linear2 where++import ADP.Fusion.Core+import FormalLanguage.CFG++++[formalLanguage|+Verbose++Grammar: Global+N: T+N: F+T: x+S: [F,F]+[F,F] -> iter   <<< [F,F] [T,T]+[F,F] -> indel  <<< [F,F] [-,x]+[F,F] -> delin  <<< [F,F] [x,-]+[T,T] -> align  <<< [F,F] [x,x]+[F,F] -> done   <<< [e,e]+//++Emit: Global+|]+++makeAlgebraProduct ''SigGlobal+

@@ -1,3 +1,8 @@+0.1.0.0+-------++- removed upper bounds+ 0.0.2.1 -------