    {- |
       Multiple alignments.

    -}

    module Bio.Alignment.Multiple

    where

    import Bio.Alignment.AlignData
    import Bio.Sequence
    -- import Bio.Clustering

    -- | Progressive multiple alignment.
    --   Calculate a tree from agglomerative clustering, then align
    --   at each branch going bottom up.  Returns a list of columns (rows?).
    progressive :: (Sequence a -> Sequence a -> (Double,EditList)) -> [Sequence a] -> [String]
    progressive = undefined

    -- |  Derive alignments indirectly, i.e. calculate A|C using alignments A|B and B|C.
    --    This is central for 'Coffee' evaluation of alignments, and T-Coffee construction
    --    of alignments.
    indirect :: EditList -> EditList -> EditList
    indirect (Repl x1 _x2:xs) (Repl _y1 y2:ys) = Repl x1 y2 : indirect xs ys -- assert x2==y1
    indirect xs@(Repl _ _:_) (Ins y1:ys)       = Ins y1     : indirect xs ys
    indirect (Repl x1 _:xs) (Del _y1:ys)       = Del x1     : indirect xs ys

    indirect (Del x1:xs) ys                    = Del x1     : indirect xs ys -- imply del+ins/=repl

    indirect (Ins _x1:xs) (Repl _ y2:ys)       = Ins y2     : indirect xs ys -- assert x1==y1
    indirect (Ins _x1:xs) (Del _y1:ys)         = indirect xs ys -- assert x1 == y1
    indirect xs@(Ins _:_) (Ins y1:ys)          = Ins y1 : indirect xs ys

    indirect [] ys                           = ys -- assert: all Ins
    indirect xs []                           = xs -- assert: all Del