Hilfestellung bei DNA Analyse

[Roin]

Hallo Leute,

ich habe neulich zufällig einen Wettbewerb gefunden, in dem man ein Programm entwerfen soll, welches DNA-Sequenzen (mit Buchstaben-Blöcken als Gene) analysieren können soll.

Der Wettbewerb ist schon einige Zeit abgeschlossen, doch als Übung ist das sicherlich nicht ganz schlecht.

Ich brauche allerdings etwas Hilfestellung bei der Herangehnsweise. Erstmal der Link zu dem Wettbewerb.
Ich habe bereits einige Funktionen zum Einlesen der Sequenzen geschrieben und Aufgabe 1 gelöst (Buchstaben ermitteln). Aufgabe 2 (Häufigkeit von einem Baustein zählen) habe ich zwar noch nicht implementiert, allerdings denke ich nicht, dass es ein großes Problem ist, da man lediglich die Sequenz in Teilsequenzen mit Trennzeichen ("Baustein") zerlegen muss und anschließend durchzählen. Ggf. kann man auch direkt die Häufigkeit des Bausteins zählen, wobei die Unterteilung in kleinere Teilsequenzen vermutkich sinnvoll ist, um später weitere Bausteine zu ermitteln.

Nun kommt meine eigentliche Schwierigkeit: Für alle folgenden Aufgaben muss ich vorher bestimmen, wie ein Baustein aussieht und dann diese ermitteln.
Ich habe zwar die Vermutung, dass ein Baustein aus 2-6 Zeichen besteht, allerdings weiß ich das nicht genau und es könnte in einer Sequenz auch Bausteine mit größerer Zeichenanzahl geben. Zudem weiß ich einfach nicht, wie ich da herangehen soll, um die Bausteine zu ermitteln. Ich KÖNNTE einfach von z.B. 6 Zeichen ausgehen und dann alle Buchstabenkombinationen durchtesten, ob diese in dem String vorkommen und immer weiter durchprobieren, bis kein Baustein mehr unidentifiziert ist, allerdings ist das so rechenaufwendig, dass ich eine effektivere Methode suche. Wie kann ich einen unbekannten Baustein bestimmen?
Ich benötige nur eine allgemeine Herangehnsweise, da ich dann den Code (vorerst) selber entwerfen möchte. Ich schreibe das Programm übrigens in Java - Java kenne ich von den nicht-webbasierten-Script-/Programmier-Sprachen am besten.

Ich würde mich über eure Hilfe natürlich sehr freuen und sobald ich das Programm fertig habe, auf euren Wunsch hin, hier veröffentlichen.

LG

 

[Timon3]

Ich sehe leider keine wirkliche Möglichkeit, das zu bestimmen. Da die Länge der Bausteine für dich nach oben nur durch die Sequenzlänge begrenzt ist, wirst du diese Aufgabe vermutlich tatsächlich brutforcen müssen. Allerdings sollte das ja kein großes Problem sein - ich würde die Länge der Bausteine einfach anfangs als 2 annehmen und dann die erste Sequenz durchtesten. Falls der Baustein 128x vorkommt, teste die anderen Sequenzen. Wenn dem so ist, Glückwunsch! Sonst teste den nächsten Baustein (also Substring eine Position nach rechts verschieben). Falls das nicht klappt, einfach die Länge des Bausteins um 1 erhöhen und weitertesten. Das wird deine beste Möglichkeit sein.

 

[Roin]

ich würde die Länge der Bausteine einfach anfangs als 2 annehmen und dann die erste Sequenz durchtesten

Wenn ich mit den "kleinen" Bausteinen beginne und dann später diese verlängere könnte es allerdings sein, dass ich bei z.B. sowas wie "ABCABCBABC" (nach AB suchen) 3 mal AB finde, der Baustein aber eigentlich ABC ist.
Da denke ich, sollte ich eher von groß nach klein testen oder nicht? Ist zwar im Zweifel mehr Rechenaufwand, daher aber sicherer.

Oder sehe ich da was falsch?

 

[KaPiTN]

Mangels mir bekannter statistischer Methoden würde ich einfach mit dem ersten Buchstaben anfangen und zählen, wie oft er vorkommt. Dann würde ich jeweils immer einen weiteren Buchstaben dazu nehmen.
Habe ich irgendwann nur doch einen Treffer, dann habe ich im Fall davor eine Sequenz. Die lösche ich aus der Gesamtmenge und beginne von vorne

Spoiler

Jetzt kann der Zufall natürlich dafür sorgen, daß n Sequenzen gleich häufig vorkommen und immer hintereinander. Also das AAbb insgesamt 23 mal vorkommt aber AA und bb zwei verschiedene Sequenzen sind. Da lassen wir jetzt mal erst mal weg

 

[theSplit]

Ich hab mich mal daran gesetzt und es in etwa so gelöst:
1) Herausfinden von simplen zweier Paaren - also DE, HG, AC usw.
2) Jetzt Kombinationen dieser Paare finden, dann DEAAD oder HGDD, bis zu der Grenze das kein Treffer mehr mit dieser Kombination oder anderen Optionen anderer Buchstaben auffindbar ist, ich bin die Buchstaben nur einmal durchgegangen jedoch mit möglichen Wiederholungen, mit diesem Anfang
3) Zusammenfassen der Kombinationen mit sich selbst und untereinander in die Bausteine

Was mir gerade dabei auffällt, es spielt nicht wirklich eine Rolle welche Bausteine oder Buchstaben man zusammen fast, sondern hinterher entstehen "überlappende" Bausteine automatisch wenn man alle Dateien zusammengefast hat. Ob die nun in dieser Form so existieren ist eine andere Frage, aber sie sind vorhanden.
Es gibt eine Kombination bei mir die heißt "DACH", taucht in jeder Datei auf, also 100 mal, dann gibt es einen anderen Baustein "CHGDD" - diese Kombination taucht auch in jeder Datei mindestens einmal auf wie auch DACH.

Was ich damit sagen will, man weiß nicht wie die Bausteinen beschaffen sind, aber man weiß in welcher Häufigkeit und Anzahl die genauen DNA Bausteine (nach dem obigen Paarungsschema) aufkommen.

Ich hoffe das hilft dir etwas, ich bin mir aber auch nicht 100% sicher ob der Gedanke der Richtige ist, aber es macht die Sache verdammt viel einfacher.
Ansonsten wäre ich natürlich auch an einer Lösung interessiert, da mein Gedanke auch komplett falsch sein kann.

Edit:
Sehe gerade das die Aufgabenstellung verlangt das man auch die Breite der Bausteine festlegen sollte, hier könnte man noch weiter zusammenführen, also alles was auftaucht nochmal mit den anderen Paaren kombinieren und suchen ob vorhanden bis man kein Treffer mehr in den Daten erhält. Erhält man keine Treffer ist ein paar komplett, vielleicht?!

 

[Roin]

Mangels mir bekannter statistischer Methoden würde ich einfach mit dem ersten Buchstaben anfangen und zählen, wie oft er vorkommt. Dann würde ich jeweils immer einen weiteren Buchstaben dazu nehmen.
Habe ich irgendwann nur doch einen Treffer, dann habe ich im Fall davor eine Sequenz. Die lösche ich aus der Gesamtmenge und beginne von vorne

Also ein einfacher Bruteforce - den wollte ich ja eigentlich vermeiden, aber bisher sieht es so aus, als müsste ich das so machen.

Jetzt kann der Zufall natürlich dafür sorgen, daß n Sequenzen gleich häufig vorkommen und immer hintereinander. Also das AAbb insgesamt 23 mal vorkommt aber AA und bb zwei verschiedene Sequenzen sind. Da lassen wir jetzt mal erst mal weg

Das Problem kann man dann ja lösen, indem man bekannte Bausteine über alle anderen herausgefunden Bausteine iterieren lässt und Kombinationen der Bausteine aus der Liste entfernt.

1) Herausfinden von simplen zweier Paaren - also DE, HG, AC usw.

Soweit verständlich und auch einfach umzusetzten.

2) Jetzt Kombinationen dieser Paare finden, dann DEAAD oder HGDD, bis zu der Grenze das kein Treffer mehr mit dieser Kombination oder anderen Optionen anderer Buchstaben auffindbar ist, ich bin die Buchstaben nur einmal durchgegangen jedoch mit möglichen Wiederholungen, mit diesem Anfang

Also einfach die 2-er-Bausteine zusammensetzten und überprüfen, ob diese vorkommen? Oder die 2er-Bausteine nehmen und anschließend mit weiteren Buchstaben erweitern (ansonsten würde man ja 3er-Bausteine nicht finden oder 5er usw....

Es gibt eine Kombination bei mir die heißt "DACH", taucht in jeder Datei auf, also 100 mal, dann gibt es einen anderen Baustein "CHGDD" - diese Kombination taucht auch in jeder Datei mindestens einmal auf wie auch DACH.

Also meinst du dann die Überlappung von CH in den Bausteinen?

---
Inzwischen habe ich eine Funktion geschrieben, die Bausteine in einer Sequenz sucht. Allerdings muss diese natürlich noch erweitert werden, sodass gefundene Bausteine gespeichert und entfernt werden. Derzeit habe ich also nur Aufgabe 2 gelöst. Ich müsste noch eine weitere Funktion schreiben, die die Bausteine zusammensetzt und überprüft.

 

[Timon3]

@Roin: Das könnte natürlich sein, dass du 3x AB findest. Aber das ist für die Aufgabe uninteressant - solange AB nicht in jeder Sequenz 128x vorkommt, wird der von mir beschriebene Algorithmus ja einfach weitersuchen, und würde dann im nächsten Durchlauf, wenn die Länge des gesuchten Steins auf 3 erhöht wird, ABC durchtesten.

 

[KaPiTN]

Also ein einfacher Bruteforce - den wollte ich ja eigentlich vermeiden, aber bisher sieht es so aus, als müsste ich das so machen.

Das war ein Schnellschuß heute Nacht, der so nicht funktionieren wird, fürchte ich. Man findet da sicher Abfolgen, die mehr als 1 mal in einer Datei vorkommen, ohne das das eine Sequenz ist, einfach als Zufall.
Vermutlich muß man mehrere Verfahren in Kombination anwenden. Da müßte man mal in Ruhe drüber nachdenken.

 

[theSplit]

@Roin:
So ganz habe ich das Problem auch noch nicht durchschaut ... daher leg bitte nicht so viel auf meinen Ansatz , ich glaube selbiger ist auch sehr fraglich und weniger zielführend da man damit nicht alle Paare aufdecken kann wie du schon schreibst.

Ich hab einen Fehler in meiner Routine gehabt die "CH" nicht entfernt hat und diese somit auch in Verbindung eines zweiten Bausteins gekommen ist. Ich bruteforce auch gerade im Kopf wie man zu einer Lösung kommt und schaue mir die Daten nochmal genauer an. Gewisse Grenzen sind ja gesetzt dadurch das "EEE" und die andere 128 Kombinationen quasi bekannt sind. Damit könnte man gewisse andere Bausteine eventuell eindämmen bzw. isolieren, wobei das auch mau aussieht.. muß anders gehen ...

Auch nochmal danke für das Posten der Seite, da hat man was um sich die Zähne auszubeißen.

 

[Roin]

Ich habe gerade mal für die Datensätze 90 bis 100 nach EEE suchen lassen und diese kommen zum Beispiel 407 oder 408 mal vor. Da lasse ich einfach alles bis auf EEE durch "" ersetzten und bestimme dann die Länge des resultierenden Strings / Länge des Blocks (3) und komme so auf meine 40x maliges Vorkommen.

Ich versuche mich nun einfach mal an einer Sequenz mit einem Bruteforce und schaue mal, wie ich das so umsetzte und was dabei so rauskommt.

EDIT:
Da sind offenitlich auch Überlappungen mitgezählt worden, die durch meine Suchmethode verursacht wurden... Alles andere zu ersetzten und so weiter klappt offensichtlich nicht so gut.

 

[theSplit]

Ich bin mir noch unschlüssig, nachdem ich 5~ Std. an dem Problem gesessen habe, wie es zu lösen, nicht mal clever aber zu lösen, ist.

Aber viel Erfolg, du kannst ja über deine Entwicklung schreiben!

Als Referenz Wert, mit Pythons Count komme ich auf 72 Instanzen des Bausteins "EEE" im ersten Datensatz.
Du kannst dir auch die Datensätze mal mit Notepad++ oder einem anderen Editor öffnen und dort zählen lassen bzw. die Anzahl Anzeigen lassen.

 

[KaPiTN]

So. Ich hatte heute Nachmittag eine Idee, die ich gerade mal ausprobiert habe

Ich unterstelle, daß ein Baustein mindestens 3 Buchstaben hat. (Da kann natürlich der erste Fehler liegen).

Also nehme ich die ersten 3 Buchstaben und zähle, wie oft diese Kombination vorkommt Dann teste ich, wie oft die Kombination vorkommt, wenn man noch einen Buchstaben dazu nimmt. Ist die Anzahl gleich, gehört der Buchstab noch zum Baustein dazu. Das ganze solange, bis das Vorkommen abnimmt.
Habe ich einen Baustein gefunden, lösche ich alle Vorkommen und beginne wieder von vorne.

Ich habe den Baustein mit 128 Vorkommen und ich habe einen Baustein 'EEE'

Da wirkt schon einmal gut, bedeutet aber noch nichts.


EFFGA;300
DEA;215
AACHG;11
EBF;128
AEG;100
EAE;48
AEA;25
AAE;93
IEA;6
DEE;13
EACHG;10
DAE;33
IDACHG;2
AEI;28
EEE;33
IEE;4

 

[theSplit]

@KaPiTN:

Die Kombination "HG" taucht drei mal in deiner Lösung auf - aber das Problem hatte ich auch, man könnte es noch teilen... oder auch nicht.
Da bin und war ich mir auch nicht sicher.

 

[KaPiTN]

Es ist sogar 'ACHG', nicht nur 'HG'.

 

[theSplit]

Ja, aber HG ist ein Bestandteil in mehreren Kombinationen und könnte ein isolierter Baustein sein.
Könnte, aber ich will auch keine Panik verbreiten

Vielleicht muss man hier noch weiter splitten um sicher zu gehen? Oder mehrere Dateien konsultieren.

Es könnte helfen andere Dateien nach genau dem gleichen Baustein zu durchsuchen, ist dieser nicht auffindbar gilt die Lösung als ungültig.

 

[KaPiTN]

Meine Ergebnis stammt aus Läufen mit 5 oder 6 Dateien.

Für EEE habe ich auch nur 33 Einträge wobei EEE unabhängig 72 Einträge hat. Es gibt ja bei mir einen Bausten mit zwei EE am Ende und andere fangen mit E an.

 

[Roin]

Nachdem ich erst den Fehler behoben habe dass ich EEE 40x mal gefunden habe (jetzt nur noch 72 mal) habe ich auch meinen Bruteforce (2-6 Zeichen) fertig.

128 mal finde ich (vermutlich immer) "EAEBF".
Ich habe bisher noch nicht Sequenzenübergreifend getestet, doch kam in 15 Sequenzen nur dieser Block eindeutig 128x vor.
Natürlich auch alle Bestandteile dieses Blocks und Kombinationen aus diesen, die ich dann aber durch ein Überprüfen mit den Längsten Blocks ausmerzen konnte.

Nun muss ich noch überlegen, wie ich meinen Code sinnvoll Sequenzübergreifend gestalte und die weiteren Blöcke herausfinde.

Derzeit sieht meine main nämlich wie folgt aus:
[src=java]public static void main(String[] args) {

String actSequenz;
String actIncLetters;
int blockCounter;
String[] block128;

Sequenz S = new Sequenz();
S.sequenz(getfileList());

while(S.existNextSequenz()) {
actSequenz = S.readNextSequenz();

//Aufgabe 1 - Buchstaben ermitteln
actIncLetters = Analyse.includedLetters(actSequenz);
System.out.println("Alle enthaltenden Buchstaben in der Sequenz sind: " + actIncLetters);

//Aufgabe 2 - Baustein zählen
blockCounter = Analyse.countBlock(actSequenz, "EEE", actIncLetters);
System.out.println("Der Block " + '"' + "EEE" + '"' + " kommt " + blockCounter + " mal in der Sequenz vor.");

//Aufgabe 3 - Baustein 128x vorkommen
block128 = Analyse.searchBlock(actSequenz, actIncLetters, 128);
for(String rBlock: block128) {
System.out.println("Der Block " + '"' + rBlock + '"' + " kommt 128 mal vor.");
}
}
}[/src]

Da bin ich mir derzeit nicht wirklich sicher, wie ich das Übergreifend testen sollte... muss vermutlich dafür ebenfalls noch neue Methoden schreiben.
Das kommt aber demnächst.

 

[theSplit]

Ich glaube meinen Quellcode poste ich nicht, sonst werde ich gesteinigt wegen unsauberen Coding-style
Versuche das ganze in Python, was die Sache vermutlich auch etwas leichter macht.

 

[Roin]

Ich glaube meinen Quellcode poste ich nicht, sonst werde ich gesteinigt wegen unsauberen Coding-style

Ich habe auch kaum Kommentare gesetzt und meine Variablen-Benennung ist grauenhaft, weil ich irgendwie alles gleich nennen will xD

Versuche das ganze in Python, was die Sache vermutlich auch etwas leichter macht.

In Python bin ich nicht so bewandert.

 

[theSplit]

Ich habe auch kaum Kommentare gesetzt und meine Variablen-Benennung ist grauenhaft, weil ich irgendwie alles gleich nennen will xD

Du kannst deinen Code ja mal in einem Spoiler posten, die Main ist ja nicht wirklich Repräsentativ was under the hood passiert.

In Python bin ich nicht so bewandert.

Dann poste ich mal meinen Code, sollte auch nicht so viel verraten, außerhalb der Konkurrenz
Der Bruteforcer um die 128 Block Combo herauszufinden ist aber mehr schlecht als Recht, tut aber seinen Dienst, ich schreib den gerade nochmal neu

Könnte aber ein wenig verraten, deßhalb auch im Spoiler!

Ist hier vielleicht jemand schon eine Idee weiter wie man die vorgehen kann um die Bausteinen zu isolieren? Als Überprüfung sollte ja das Geschlechtsgen ersichtlich werden wenn ich die Aufgabenstellung richtig verstehe oder gibt es noch mehr Hinweise?

*Edit:
Lösung stimmt nicht.

Spoiler

[src=python]
from time import sleep


# Read initial data file for sampling
filehandle = open("resultset1i.txt", "r");
dnaData = filehandle.read();
filehandle.close();

# Create the initial dictionary
alphabet = [];
for char in dnaData:
if char not in alphabet:
alphabet.append(char);

alphabet.sort();

# Count EEE blocks in file
# A simple count would be enough,
# but this would mean cheating
eeeData = dnaData;
eeeCount = 0;
while(True):
position = eeeData.find("EEE");
if (position != -1):
eeeCount += 1;
eeeData = eeeData.replace("EEE", "", 1);
else:
del eeeData;
break

print("EEE count in file: %d" %(eeeCount));

# Find 128 times block using combinations
block128 = "";

# Create the combinations to avoid single letter
# brute forcing which would not work easily
combinations = [];

for letter in alphabet:
for combination in alphabet:
combinations.append(letter + combination);

# The brute store
bruteDictionary = [];
bruteAlphabet = [];
bruteLength = 0;

# Find 128 occuring combinations for hinting
for combination in combinations:
if (dnaData.count(combination) == 128):
bruteDictionary.append(combination);

# Prepare brute alphabet of found combinations
for combination in bruteDictionary:
for letter in combination:
if not letter in bruteAlphabet:
bruteAlphabet.append(letter);
bruteLength += 1;

searchString = "";
hasBlock = False;
hasPreviousBlock = False;
exitBrute = False;
rounds = -1;
subRounds = 1;


print("\nBruting using the following alpabet:");
print(bruteAlphabet);

while(True):
for letter in bruteAlphabet:
searchString += letter;
print(searchString);
sleep(0.1);
count = dnaData.count(searchString);
if (count == 128):
hasBlock = True;
hasPreviousBlock = True;
block128 = searchString;
print("- 128 Combo found using: %s -" %(searchString));
rounds = 0;
else:
hasBlock = False

if (rounds == -1):
searchString = searchString[:-1];
else:
if not (hasBlock):
if (rounds >= len(bruteAlphabet)-1):
if (len(block128) >= bruteLength):
exitBrute = True;
break;
else:
if (subRounds > len(bruteAlphabet)-1):
subRounds = 0;
searchString = bruteAlphabet[subRounds];
hasPreviousBlock = False;
rounds = -1;
subRounds += 1;
else:
searchString = bruteAlphabet[rounds];

if (hasPreviousBlock):
searchString = block128;



if (exitBrute):
break;

rounds += 1;

print("Block128 = %s" %(block128));
[/src]