Re: [Seqan-dev] Lokales Banded-Alignment

["Rausch, Tobias" <Tobias.Rausch@fu-berlin.de>]

Hallo Hannes,

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

Ja.

> Obwohl ein lokales Banded ja auch nicht so sinnvoll ist, wie 
> ein (semi-)globales Banded....

Also wenn du den kompletten Read in einem Ausschnitt vom Genom finden willst (semi-global),
dann geht das mit dem AlignConfig. Setze das genom als 1. string und
den read als 2. und nehme AlignConfig<true, false, false, true>.

> David meinte 
> die Fragmente seien die exakten Stücke des Alignments, so 
> dass ich vor dem ersten Fragment und nach dem letzten 
> "abschneiden" kann.

Die Fragmente sind im Sinne der DP-Matrix alle Diagonalen, also Matches UND Mismatches.
Aufgrund des tracebacks kommen die Fragmente im 
String<Fragment<> > alle rückwärts.
Ein einzelnes Fragment hat 5 members, die id des 1. strings, die begin position
im 1. string, die id des 2. strings, die begin position im 2. string
und die laenge des matches. Demnach ist


> 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

obiges Alignment zwar ein Alignment vom gleichen Score, der traceback ging aber so:

> Query: 0   AGCCATTAGAGGCCACCACACCAGACG 27
>             ||||||||||||||||||||||   |
> Sbjct: 214 GGCCATTAGAGGCCACCACACCA---G 238

Bei mehreren gleich guten Alignments wird zufaellig ein traceback genommen.
Mit AlignConfig<true, false, false, true> sollte dein oberes Alignment rauskommen.

Grüße,
Tobias




> -----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 5:06 PM
> An: Rausch, Tobias
> Cc: 'seqan-dev@lists.fu-berlin.de'; 'David Weese'
> Betreff: Re: [Seqan-dev] Lokales Banded-Alignment
> 
> 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
> 
> _______________________________________________
> seqan-dev mailing list
> seqan-dev@lists.fu-berlin.de
> https://lists.fu-berlin.de/listinfo/seqan-dev
>