Semi Global Alignment

Question

[Maria]

hello,

I'm trying to write a code to algin 2 sequences where gaps are for free in the beginning and the end of the second sequence i.e.

s1 = CATACGTCGACGGCT
s2 = ACGACGT**AAAAC**

Alignment:

CATACGTCGACGGCT
---ACGACGT-----------

I need to stop at some point(T for example) in s2 where the two sequences don't match anymore ( global alignment with free gaps at start and end)

I used a semi global alignment approach s1 in row, s2 in column , initialize the first row to 0 , initialize the 1st column as gaps accumulation

Questions :1- what is the best way to chose the beginning of trace back , is it the maximum of the last row ? 2- for this problem filling the matrix is like local alignment (minimum =0) or like the global one ore negative values are allowed ?

[Spitshine]

There's nothing bold in s2.

[Maria]

check the right part now

Answer 1

[audrius.meskauskas]

This looks much more like local alignment for me (no start/end gap penalty). May be this is the right algorithm for you?

[Niek De Klein]

local also sets all negative scores to 0. If you only want no start/end gap penalties it is semi-global

Answer 2

[brentp]

I think what you're looking for is global alignment with cost-free-ends.

You can try various strategies with this module: https://github.com/brentp/align

Here's an example script:

s1 = "CATACGTCGACGGCT"
s2 = "ACGACGTAAAAC"

from align import aligner

for method in ("global_cfe", "glocal", "local", "global"):

    print "-" * len(method)
    print method
    print "-" * len(method)
    print "\n".join(aligner(s1, s2, method=method))
    print

which creates the following output:

----------
global_cfe
----------
CATACGTCG-ACGGCT
---ACGACGTAAAAC-

------
glocal
------
ACGTCG-ACGGC
ACGACGTAAAAC

-----
local
-----
ACGTCG-ACGGC
ACGACGTAAAAC

------
global
------
CATACGTCGACGGCT
ACGACGTAAAA--C-

[Maria]

thank you for your answer, I'm interested in the first one (global cfe) where can find how the algorithm works ?

[Maria]

i;m trying to implement under perl