[gelöst]DNA Sequenz

Dr. Evil

Hallo

Hab jetzt zu folgendem Problem lang gesucht aber irgendwie nichts verständliches gefunden.Ich habe eine zweidimensionales Array:

char kette1[2][10]={"ATTCG","TGAGTTCATA"};

wobei beides DNA Sequenzen darstellen sollen.Jetzt soll ATTCG mit TGAGTTCATA abgeglichen werden und die größte zusammenhängende Zeichenketten gefunden werden.
Optisch erstmal ja TTC, nur wie setzte ich das in einem C Programm um!?
Da ich ja das Array mit dem Inhalt der beiden Strings gefüllt habe bzw. die Grösse mit (2) Zeile (10) Spalten festgelegt ist,wir zähle ich den Index der Arrays hoch?
Ich müsste ja quasi bei kette[0][0]anfangen, die mit kette [1][0] auf Gleichheit prüfen.Bei Ungleichheit inkrementiere ich dann den Index der zweiten Sequenz,bei Gleichheit speichere ich die Position und inkrementiere ebenfalls die zweite Sequenz.Nach dem ersten Durchlauf inkrementiere ich dann den Index der ersten Sequenz und fahre so weiter fort.
Hoffe ich konnte erstmal halbwegs verständlich erklären was ich vor habe.
Vielleicht hat jemand von euch so etwas mal in C gemacht bzw. einen Lösungsansatz.
Auch wenn ich dafür jetzt auf der Wand der Helden landen sollte , hier das was bis jetzt so mit eher mäßigen Erfolg durch den Compiler ging:

main()
{
    int j,i;

    char *pointer;

char kette1[2][10]={"ATTCG","TGAGTTCATA"};

pointer=kette1;

for (kette1[i][j=0];j<9;j++)
{
    printf("%c\n",*pointer++);
    }

(Wobei man wie bereits geschrieben nur von einem Lösungsansatz reden kann.)

nwp2

Hmm, eine Fertiglösung gibt es dafür glaube ich nicht.

Je nachdem wieviel Mühe du dir machen willst und wie schnell es laufen soll gibt es da verschiedene Möglichkeiten.

Der naive Ansatz:

int i, max = 0; //max ist die Länge des momentan am längsten gefundenen Teilstrings
char *temp, t, longest = 0; //temp ist jeweils ein Teilwort von kette1[0] und wird mit kette1[1] verglichen
 //longest ist der längste gefundene Teilstring
for(temp = kette1[0], i = 0; *(kette1[0]+i) && strlen(kette1[0]+i)>max; i++){
    if (t = strstr(temp, kette1[1]){
        longest = t;
        max = strlen(kette1[0]+i);
    }
}

Das sucht dir schonmal das längste Vorkommen von ATTCG, TTCG, TCG ...

Danach ersetzt du das letzte Zeichen mit einem '\0'-Zeichen und beginnst von vorn.

Funktioniert und ist ohne viel Hirnschmalz implementierbar.

Wenn es schnell gehen muss baust du dir entweder einen DFA oder bastelst eine Spezialform vom KMP-Algorithmus, wobei mir der DFA spontan mehr zusagt. Findest du bei Wiki. Da muss man aber einen Moment länger überlegen und das solltest du erst machen wenn du in ernsthafte Performance-Schwierigkeiten kommst.

spjoe

Tipp: da gibts nette prolog algos über sowas

Dr. Evil

Danke @ nwp2
Musste mich zwar ein wenig einarbeiten, aber der KMP-Algorithmus war genau das was ich gesucht hab.