Question: Semi Global Alignment
2
8.0 years ago by
Maria170
Maria170 wrote:

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 ?

• 4.7k views
modified 8.0 years ago by brentp23k • written 8.0 years ago by Maria170

There's nothing bold in s2.

check the right part now

0
8.0 years ago by
audrius.meskauskas100 wrote:

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

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

0
8.0 years ago by
brentp23k
Salt Lake City, UT
brentp23k wrote:

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-
``````

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