Was uns Computer nicht über ökologische und evolutionäre Dynamiken sagen können

In einem Artikel, der in dieser Woche in der Fachzeitschrift Proceedings of the National Academy of Sciences (PNAS) veröffentlicht wurde, entdecken Rasmus Ibsen-Jensen, Postdoc am Institute of Science and Technology Austria (IST Austria), IST Austria Professor Krishnendu Chatterjee und Professor Martin A. Nowak von der Harvard Universität überraschende Verbindungen zwischen den Computerwissenschaften und der Biologie, also zwischen zwei Disziplinen, die sich unter anderem damit befassen, wie sich Information zeitlich und räumlich ausbreitet.

Die Autoren beschäftigten sich konkret mit der Komplexitätstheorie – einem Gebiet, das sowohl in der theoretischen Informatik als auch in der Mathematik eine Rolle spielt. In ihr werden algorithmisch behandelbare Probleme und deren Komplexität anhand ihrer Schwierigkeit klassifiziert.

Die Wissenschaftler untersuchten mittels dieser klar definierten Komplexitätsklassen einige fundamentale Fragen der theoretischen Biologie, und zwar die ökologische und evolutionäre Dynamik innerhalb von strukturierten Populationen. 

Wie kann man beispielsweise die Wahrscheinlichkeit dafür bestimmen, dass sich eine neue genetische Mutation in einer Population durchsetzt oder eine invasive Art eine ökologische Nische erobert? Diese Fragen sind zwar gut untersucht, aber selbst für diese wichtigen Problemstellungen fehlte ein Verständnis der Berechnungskomplexität.

Die Forscher fanden den eher unerwarteten Beweis dafür, dass sich diese fundamentalen Fragen in der Ökologie und Evolution von bestimmten Komplexitätsklassen präzise charakterisieren lassen, ganz so als würden die evolutionären Prozesse Aspekte der Informatik nachahmen. Durch die exakte Bestimmung der Komplexitätsklassen gelang ihnen der formale Beweis dafür, dass diese Fragen nicht mit einer einfachen Formal lösbar sind.

Die Autoren konnten jedoch auch aufzeigen, dass es für zwei klassische Fragestellungen tatsächlich effiziente Lösungen zur Berechnung geben muss: Zum einen für die „Molekulare Uhr“, einer Methode, bei der der Zeitpunkt der Aufspaltung zweier Arten von einem gemeinsamen Vorfahren abgeschätzt wird. Und zum anderen die Fixierungswahrscheinlichkeit, also die Chance einer genetischen Variation, sich in einer gut durchmischten Population durchzusetzen.

Wie also gelang es den Forschern mit Sicherheit zu sagen, dass manche Fragen mittels Algorithmus lösbar sein müssen? Und wie kann man behaupten, für andere Fragen gäbe es keine derartige Lösung?

Die Wissenschaftler verwendeten anerkannte Methoden aus der Komplexitätstheorie und übertrugen sie auf definierte evolutionäre Szenarien in den Bereichen der Evolutionären Spieltheorie und der Evolutionären Graphentheorie. Daraus resultierend konnten sie die exakten Komplexitätsklassen für jede dieser Forschungsfragen ableiten. Durch die Zuordnung zu einer spezifischen Komplexitätsklasse kann man nämlich exakt sagen, ob ein effizienter Algorithmus existieren muss oder nicht. Wie ist das möglich?

Man stelle sich zum Beispiel ein Puzzle mit gigantischen Ausmaßen vor. Wenn es dafür eine Vorlage gibt, lässt sich genau sagen, wo welches Teil hingehört; man kann das Puzzle einfach lösen und danach feststellen, dass es tatsächlich mit dem Bild auf der Schachtel übereinstimmt. Die Komplexitätstheorie bezeichnet diesen Typus von Problemstellungen mit P, da die Fragen in Polynomialzeit lösbar sind. Unter anderem enthält P alle Probleme, die mittels einfacher Formel lösbar sind. Es gibt aber viele Probleme, die nicht in Polynomialzeit lösbar sind, weil die dafür nötigen Rechenkapazitäten mit zunehmender Größe des Input exponentiell ansteigen würden. Es existiert daher keine einfache Formel für solche Probleme.

In diesem Zusammenhang ist auch eine weitere Komplexitätsklasse von Bedeutung, nämlich NP (nichtdeterministische Polynomialzeit). Diese umfasst Probleme, deren Lösung in Polynomialzeit auf Richtigkeit überprüft werden kann. Denken wir wieder an das überdimensionale Puzzle zurück, nur diesmal ohne Anleitung. Die Entscheidung, wo welches Teil hingehört kann sich jetzt recht schwierig gestalten. Aber sobald man das Puzzle gelöst hat, lässt sich wie oben erwähnt sehr einfach feststellen, ob das Ergebnis richtig ist.

Übrigens zählt die Frage, ob alle NP Probleme in der Klasse P enthalten sind oder nicht zu den sechs berühmten noch ungelösten Problemen der Mathematik, für dessen Lösung das Clay Mathematics Institute im Jahr 2000 den Millenium Prize in Höhe von 1 Million Dollar ausgeschrieben hat. Auch wenn die Frage nach wie vor nicht gelöst ist, wird allgemein angenommen, dass P ungleich NP ist, was bedeuten würde, dass die schwierigsten Probleme in NP nicht mit einer einfachen Formel lösbar sind.

Die Erkenntnisse aus der Forschungsarbeit sind ein erster Schritt, um Verbindungen zwischen den beiden Disziplinen Informatik und Biologie zu schaffen. Zudem zeigt die Arbeit auf, dass sich die Forschung zu bestimmten Fragestellungen in der ökologischen und evolutionären Dynamik auf diejenigen Aspekte fokussieren sollte, die rechnerisch mit einer einfachen Formel lösbar sind.