Re: [Seqan-dev] Lokales Banded-Alignment
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
>
