Re: [Seqan-dev] Lokales Banded-Alignment

[Hannes Hauswedell <hauswedell@mi.fu-berlin.de>]

Hallo Tobias,

danke für die schnelle Antwort!

Am Dienstag, 18. August 2009 09:46:41 schrieb Rausch, Tobias:
> Hallo Hannes,
>
> > Käme ich im Nachhinein noch an den Score an der Stelle x,y in der
> > DP-Matrix dran?
>
> Leider nein, Gotoh, BandedGotoh & Co. speichern alle immer nur eine
> Spalte bei der Berechnung um Memory zu sparen.

Hm, macht Sinn.

> > localAlignment() kann ich dafür nicht verwenden, weil das kein
> > Gotoh und erst Recht kein BandedGotoh unterstützt.
>
> Der SmithWaterman hinter dem localAlignment() verwendet lineare
> Gapkosten ist also ein "Gotoh-Style" Algorithmus.

Da kann ich auch andere gapOpen, als gapExtend-Kosten angeben?

> Was in der Tat noch
> fehlt in SeqAn ist ein BandedSmithWaterman.
>
> > Das Problem hierbei ist, das auch mit dieser AlignConfig, das
> > Max nur in letzter Zeile und Spalte, nicht aber "mittendrin"
> > gesucht wird (die Funktion ist schließlich "globalAlignment").
>
> Ja stimmt, was du vermutlich brauchst ist der BandedSmithWaterman und
> den gibt es leider noch nicht, sorry.

Obwohl ein lokales Banded ja auch nicht so sinnvoll ist, wie ein 
(semi-)globales Banded, da bei einem wirklich lokalen Alignment die 
Wahrscheinlichtkeit ja auch nicht höher ist im Band / in Entfernung k um 
die Hauptdiagonale zu sein, als irgendwo anders. Insofern ist das 
Problem vielleicht viel tiefer und die Frage ob wir wirklich on lokales 
Alignment wollen, und wenn ja, dass wir es dann anders realisieren 
müssen.
Aber da kann mir nur David weiterhelfen, denke ich.

Bezüglich dem globalAlignment und der Rückgabe von Fragmenten habe ich 
aber noch einige Verständnissprobleme. David meinte die Fragmente seien 
die exakten Stücke des Alignments, so dass ich vor dem ersten Fragment 
und nach dem letzten "abschneiden" kann um "lokaler" zu werden. In der 
Realität bekomme ich aber ganz andere "unlokale" Ergebnisse, z.B:

Query: 0   AGCCATTAGAGGCCACCACACCAGACG 27
            |||||||||||||||||||||||   
Sbjct: 214 GGCCATTAGAGGCCACCACACCAG--- 238

Die Fragmentinformationen:
FRAGMENT 0:             read begin: 26  geno begin: 237 length: 1
FRAGMENT 1:             read begin: 0   geno begin: 214 length: 23

Woher kommt da das 0te Fragment, und wieso beginnt das erste mit einem 
Mismatch? (Hier ist der Read vollständig also semiglobal aliniert)

Ein anderer Hit ist wiederum tatsächlicher lokaler, endet jedoch auch 
mit einem MisMatch:

Query: 6   CCATTAGAGGCCACCACACCG 27
           |||||||||||||||||||| 
Sbjct: 216 CCATTAGAGGCCACCACACCA 237

Unabhängig von den Fragmenten, bezieht sich der Score auch auf das echte 
globale Alignment, weicht also von dem hier gezeigten stark ab.

Das wäre ein weiterer Grund warum das Verfahren ungeeignet ist, wobei 
ich natürlich Alignments die den Read nicht vollständig enthalten ein 
zweites Mal scoren könnte (was im Endeffekt - wie erwähnt - dann aber 
wahrscheinlich den Geschwindigkeitsvorteil vom Banded kaputt macht).

Danke für die Hilfe,
Gruß,
Hannes

>
> > -----Ursprüngliche Nachricht-----
> > Von: seqan-dev-bounces@lists.fu-berlin.de
> > [mailto:seqan-dev-bounces@lists.fu-berlin.de] Im Auftrag von
> > Hannes Hauswedell
> > Gesendet: Tuesday, August 18, 2009 1:09 AM
> > An: David Weese
> > Cc: seqan-dev@lists.fu-berlin.de
> > Betreff: [Seqan-dev] Lokales Banded-Alignment
> >
> > Hallo David und andere,
> >
> > ich versuche bei mir ein lokales Banded-Alignment mit Gotoh
> > zu machen.
> > Dafür benutzte ich bis jetzt:
> >
> > TScoreValue myScore = globalAlignment(result_frags, pairSet,
> >                                       options.blastScoring,
> >
> > AlignConfig<true,true,true,true>(),
> >                                       diagLow, diagHigh,
> >                                       BandedGotoh() );
> >
> > Das Problem hierbei ist, das auch mit dieser AlignConfig, das
> > Max nur in letzter Zeile und Spalte, nicht aber "mittendrin"
> > gesucht wird (die Funktion ist schließlich "globalAlignment").
> > Ich könnte natürlich von Beginn des ersten Fragments bis zum
> > Ende des letzten nochmal global scoren, aber das ist ein
> > extra Aufruf, der das Gesamte noch weiter bremst (dieser
> > Funktionsaufruf ist jetzt schon der Bottleneck).
> >
> > localAlignment() kann ich dafür nicht verwenden, weil das
> > kein Gotoh und erst Recht kein BandedGotoh unterstützt.
> >
> > Was kann man da tun? Käme ich im Nachhinein noch an den Score
> > an der Stelle x,y in der DP-Matrix dran? x,y wäre hierbei das
> > Ende des letzten Fragments (bzw. wegen reverser Orientierung,
> > des ersten).
> >
> > Vielen Dank,
> > Hannes
> >
> > _______________________________________________
> > seqan-dev mailing list
> > seqan-dev@lists.fu-berlin.de
> > https://lists.fu-berlin.de/listinfo/seqan-dev

-- 
Solidarische Grüße
Hannes