5

我编写了使用 Smith-Waterman 算法解决局部对齐问题的代码。

我想通过输入长度为 10000 的字符串、合理的内存（低于 2GB 内存）和合理的时间（低于 5 分钟）来做到这一点。

起初我为此使用了 bio 库的内置函数，它运行得太慢了，在我杀死它之前吃掉了 4GB 的内存。

注意java程序jAligner，实现了同样的算法，不到1GB的内存，不到20秒就可以解决这个问题。

当我写了一个未装箱的版本时，程序给了我<<loop>>. 我认为这是因为数组需要在数组完全构建之前访问数组中的项目。

所以我想知道是否有可能为这种更大的动态编程问题编写具有相似性能的 Haskell 代码。

module LocalAlign where
--import Data.Array.Unboxed
import Data.Tuple
import Data.Array


localAffineAlignment :: (Char -> Char -> Int)
                                    -> Int
                                    -> Int
                                    -> String
                                    -> String
                                    -> (Int, (String, String, String, String))
localAffineAlignment f g e s' t' = (score, best) where
    n = length s'
    m = length t'
    s= array (0,n-1) $ zip [0..n-1] s'
    t= array (0,m-1) $ zip [0..m-1] t'
    table :: (Array (Int,Int) Int,Array (Int,Int) Int)
    table   = (c,d)
      where --a :: UArray (Int,Int) Int
          a = array ((0,0),(n,m)) [((x,y),a' x y)|x<-[0..n],y<-[0..m]] --s end with gap
          b = array ((0,0),(n,m)) [((x,y),b' x y)|x<-[0..n],y<-[0..m]] --t end with gap
          c = array ((0,0),(n,m)) [((x,y),fst (c' x y))|x<-[0..n],y<-[0..m]] -- best 
          d = array ((0,0),(n,m)) [((x,y),snd (c' x y))|x<-[0..n],y<-[0..m]] -- direction
          a' i j
            | i==0 || j==0  = inf
            | otherwise     = max (a!(i-1,j)-e) (c!(i-1,j)-g-e)
          b' i j
            | i==0 || j==0  = inf
            | otherwise     = max (b!(i,j-1)-e) (c!(i,j-1)-g-e)
          c' i j
            | min i j == 0  = (0,0)
            | otherwise     = maximum [(b!(i,j),3),(a!(i,j),2),(c!(i-1,j-1) + f u v,1),(0,0)]
            where u = s!(i-1)
                  v = t!(j-1)
          inf = -1073741824
    score :: Int
    score = maximum $ elems $ fst table
    best :: (String, String, String, String)
    best = (drop si $ take ei s',drop sj $ take ej t',b1,b2)
      where (a,d') = table
            (si,sj,b1,b2) = build ei ej [] []
            (ei,ej) = snd $ maximum $ map swap $ assocs a
            build x y ss tt
             | o == 0       = (x,y,ss,tt)
             | d == 1       = build (x-1) (y-1) (u:ss) (v:tt) 
             | d == 2       = build (x-1) y     (u:ss) ('-':tt) 
             | otherwise    = build x (y-1)     ('-':ss) (v:tt) 
             where o = a!(x,y)
                   d = d'!(x,y)
                   u = s!(x-1)
                   v = t!(y-1)
4

2 回答 2

10

甚至有可能为这种更大的动态规划问题编写具有相似性能的 Haskell 代码。

是的当然。使用相同的数据结构和相同的算法，您将获得相同（或更好，或更差，取决于常数因素）的性能。

您正在大量使用（中间）列表和盒装数组。考虑改用矢量包。

于 2012-12-12T20:50:02.253 回答
2

您可能对MemoCombinators 库感兴趣，它使动态编程变得更加容易。您基本上可以在没有记忆的情况下编写算法，然后只需注释您想要记忆的变量，编译器就会从那里获取它。

于 2012-12-13T04:25:37.207 回答