Re: [Seqan-dev] about the best local alignment using BandedSmithWaterman

[Manuel Holtgrewe <manuel.holtgrewe@fu-berlin.de>]

Hi Beifang,

On 11/11/2011 01:02 AM, Beifang Niu wrote:
> Hi Seqan,
>
> There is one function "localAlignment" in the Seqan tutorial.
> Are there only three tags "BandedWatermanEggert
> <file:///C:/Users/beifang/Desktop/Seqan_Release_1.3/doc/TAG_Local+_Alignment+_Algorithms.html>,
> SmithWaterman
> <file:///C:/Users/beifang/Desktop/Seqan_Release_1.3/doc/TAG_Local+_Alignment+_Algorithms.html>,
> WatermanEggert
> <file:///C:/Users/beifang/Desktop/Seqan_Release_1.3/doc/TAG_Local+_Alignment+_Algorithms.html>"
> ?  I am wondering why there is no BandedSmithWaterman tag?
>
> If I want to computes the best local alignment of two sequences using
> banded smithWaterman algorithm with fixed band length (for example: band
> length = 10 ),  Can I use LocalAlignment function to do that?

There is a BandedSmithWaterman tag and there is a localAlignment() 
function for it. I'm no expert in this part of SeqAn, but you could have 
a look at the source in align/align_local_dynprog_banded.h and give it a 
try.

> I have another question about the alignments and seed extension in the
> Seqan library.  It seems that there is no any parameter or return value
> for alignment identity ( matched base/ alignment length ) and the
> sequence identity of seed extension part (matched base / extension part
> length ).
> Although, users can parse the alignment results or rewrite the seed
> extension code to get the sequence identity,  I still hope I can get
> sequence identity directly from alignments or seed extension results.

I think the main problem here is how seeds work:

The Simple Seed does not store any alignment information, it only 
consists of start/end coordinates in both sequences together with a 
score. It is not stored yet how any gaps look like.

The Chained Seed stores lists of diagonals. However, we have not yet had 
much use for it in seeds2, so the extension algorithm has not been 
written for it yet.

There is a comment in seeds2/seeds_extension.h (around line 730) that 
describes how this could be implemented. The main challenge here is that 
the extension algorithm itself only gives you a score and the new 
begin/end coordinates in the sequences. You would have to implement 
banded alignment and extract the matching diagonals from the alignment.

When you are using Chained Seeds then a iteration over its diagonals can 
give you an alignment, sequence identity etc. etc.

We would welcome a tested patch with this functionality.

Bests,
Manuel