Ausrichten mehrerer Sequenzen in einer heterogenen Gruppe

Sie können dies versuchen:

• BLAST jede Sequenz zu jeder anderen Sequenz (paarweise).
• Jede Ausrichtung (mit einem definierten Cutoff) bezeichnet eine Verbindung.
• Ordnen Sie alle Verbindungen zu.
• Wenn eine Sequenz direkt oder indirekt mit einer anderen verbunden ist, fällt sie in eine Gruppe. Setzen Sie alle Sequenzen, die seq1ausgerichtet sind, in Gruppe-1 , und gehen Sie dann zu den Ausrichtungen dieser Sequenzen; fügen Sie alle Sequenzen, an denen diese ausgerichtet sind, erneut in Group-1 ein ; Bevölkern Sie die Gruppe also weiterhin so.

Methodik:

• Installieren Sie eigenständiges Blast (wenn Sie nicht viele Sequenzen haben, können Sie BLAST auch online ausführen)
• Erstellen Sie eine Explosionsdatenbank aus Ihren Sequenzen mitmakeblastdb
• Gleichen Sie diese Sequenzen mit der Datenbank ab. Wenn Sie Online-BLAST verwenden, verwenden Sie BL2seq (zwei Sequenzen ausrichten). Es ist viel besser und bequemer, eigenständig zu verwenden. Sie können auch angeben, ob Sie Plus-Plus- oder Plus-Minus-Ausrichtungen oder beide Ausrichtungen wünschen. In einigen Fällen möchten Sie möglicherweise nur eines der beiden.
• Im eigenständigen BLAST können Sie das Ausgabeformat angeben (welche Felder enthalten sein sollen usw. Das von Ihnen gewählte Format hängt nur von Ihren Anforderungen ab).

Ein tabellarisches Ausgabeformat sieht etwa so aus:

# BLASTN 2.2.27+
# Query: TCONS_00036712 gene=XLOC_017996
# Database: ../nt_db/nt
# Fields: query id, subject id, % identity, alignment length, mismatches, gap opens, q. start, q. end, s. start, s. end, evalue, bit score
# 1014 hits found
TCONS_00036712  gi|191174875|emb|CU655970.6|    95.54   202 9   0   423 624 16680   16479   8e-85    324
TCONS_00036712  gi|51491599|gb|AC144709.2|  95.02   201 10  0   424 624 28443   28243   1e-82    316

Ignorieren Sie die kommentierten ( #) Zeilen; das erste Feld ist die Abfrage-ID, das zweite die Betreff-ID und es gibt eine Ausrichtung zwischen den beiden; die anderen Felder geben Auskunft über die Ausrichtung (Sie können diese Felder auswählen).

Zum Parsen verwende ich eine schnelle und einfache Skriptsprache namens awk, die in allen UNIX-basierten Systemen enthalten ist. Es ist auch für Windows im GNUWin32-Paket verfügbar.

Was Sie tun müssen, ist die ersten beiden Felder zu überprüfen und die Gruppe zu aktualisieren.

# MakeGroups.awk

BEGIN{FS="\t"} # Feldtrenner als Tab deklarieren

!($1 in grp){ # Prüfe, ob seq eine übergeordnete Gruppe ist. Wenn nicht...
    k=1
    für(ich in grp){
        if($1 in grp[i]){ # Prüfe, ob seq Teil einer anderen Gruppe ist
            parentgrp[$1]=i
            if(!($2 in grp[i])) # Prüfe, ob das zweite Feld, dh Betreff, bereits in der Elterngruppe vorhanden ist
                grp[i][$2] # Wenn nicht, weisen Sie das zweite Feld der übergeordneten Gruppe zu
            k=0
            break # Hör auf, weiter zu suchen
        }
    }
    if(k==1) # Es gibt keine übergeordnete Gruppe mit diesem Label und die seq ist kein Teil einer anderen Gruppe
        grp[$1][$1] # Erstellen Sie eine Gruppe mit der Abfrage-ID als Bezeichnung und fügen Sie diese Abfrage dieser Gruppe hinzu.
}  

$1 in Grp{
    if(!($2 in grp[$1]))
        grp[$1][$2] # Wenn das zweite Feld kein Teil der Gruppe mit dem ersten Feld als Label ist, dann weisen Sie es diesem zu
}

ENDE{
    für(ich in grp){
        x++
        print "Gruppe-"x"\n----------"
        for(j in grp[i])
            drucke j
    }
    drucke "\n"
}

Führen Sie dieses Skript wie folgt im Terminal aus:
gawk -f MakeGroups.awk blastalignmentfile.txt

Hinweis: Dieses Skript enthält mehrdimensionale Arrays. Es funktioniert nicht mit allen Versionen von awk. Verwenden Siegawk version >4.0 .

Wie swarnbes in ihrer Antwort erwähnt, gibt es schnellere Algorithmen, die diese Art von Dingen erledigen und für die Sequenzzusammenstellung verwendet werden. Viele von ihnen erstellen einen Graphen (Netzwerke, die als deBruijn-Graphen bezeichnet werden), in denen jede Verbindung eine Ausrichtung ist, und berechnen einen Eulerschen Pfad. Siehe diese Rezension von Pavel Pevzner für Details. Überlappende Sequenzen bilden Contigs und Sie können leicht zurückverfolgen, welche Sequenz von welchem ​​Contig stammt (was Sie als Gruppe bezeichnen können). Jeder Contig/jede Gruppe ist ein disjunkter deBruijn-Untergraph.

Brauchen Sie BLAST wirklich? Das heißt, sind die Sequenzen so unterschiedlich, dass Sie einen Algorithmus benötigen, der nach großen Unterschieden zwischen ihnen sucht?

Vielleicht könnten Sie so etwas wie Phrap verwenden, das Contigs für Sie zusammenstellen sollte, wenn die Sequenzen, die zusammengehören sollen, sehr nahezu identisch sind.