Turing Award-winnaar Richard Karp was al ver in de vijftig toen hij overstapte van de theoretische informatica naar de bioinformatica. Hij leerde hoe belangrijk het is om met biologen samen te werken, in plaats van om in zijn eentje een rekenprobleem te kraken.
‘De natuur rekent’, is de kortste samenvatting die de Amerikaanse informaticus Richard Karp van zijn huidige werk geeft. Hij ontwikkelt rekenmethoden – algoritmen – die biologen kunnen gebruiken bij het ontrafelen van de geheimen van het leven. Geheimen als hoe de moleculaire machinerie van een cel werkt, of wat de genetische overeenkomsten zijn tussen organismen die in de loop van de evolutie uit elkaar zijn gegroeid.
Karp was begin juni een dag te gast in Amsterdam bij het Centrum Wiskunde & Informatica, ter gelegenheid van de officiële start van de CWI-onderzoeksgroep Levenswetenschappen. CWI-wiskundigen en -informatici uit deze groep gaan structureel samenwerken met biologen in een aanpak die systeembiologie heet. Karp is voor hen een levende legende, dankzij zijn baanbrekende werk in de ontwikkeling van combinatorische algoritmen.
Traditioneel dreef de biologie op kwalitatieve modellen. Maar binnen de systeembiologie zijn biologen, fysici, chemici, wiskundigen en informatici sinds een jaar of tien geleidelijk aan meer gaan samenwerken aan het modelleren van hoe grote hoeveelheden moleculen in tijd en ruimte samenwerken in de levende cel. En dat zijn kwantitatieve modellen. De biologen zijn goed in het meten aan levende organismen en in het klassieke kwalitatieve biologische begrip. De fysici hebben veel ervaring met het modelleren van complexe systemen, terwijl informatici en wiskundigen een uitgebreide expertise hebben in het bouwen en rekenkundig analyseren van systemen waarin alles met alles samenhangt.
Richard Karp had al een rijke loopbaan als theoretisch informaticus achter de rug, toen hij in de jaren negentig als een van de eerste informatici overstapte naar de bioinformatica. Hij was toen al ver in de vijftig.
Naïef
“Het ontrafelen van het menselijk genoom was in die jaren hot”, vertelt Karp over de reden van zijn overstap. “Ik zag informatici aan dit probleem werken waarvan ik dacht: als zij het kunnen, dan kan ik het ook. Daarnaast was ik een beetje moe van het werken op het terrein van de metatheorie, wat ik jarenlang had gedaan. Ik wilde met mijn kennis van algoritmen iets doen wat praktisch toepasbaar was, en de biologie leek me de beste toepassing daarvan.”
Zijn overstap ging niet zonder slag of stoot. Karp dacht dat het genoeg zou zijn om goede algoritmen te ontwikkelen, iets wat hij al heel zijn leven deed. Naïef gedacht, zo bleek. “Mijn werk uit de jaren negentig aan het ontrafelen van de DNA-volgorde heeft in de praktijk geen invloed gehad. Wetenschappelijk werkte het wel, maar ik had te weinig rekening gehouden met de sociale context die nodig is om je werk toe te passen. Nu weet ik dat je ook op promotiecampagne moet gaan. Je moet samenwerken met de DNA-sequencingcentra; je moet samen met biologen naar de data kijken; je moet hen ervan overtuigen dat je nuttig voor ze kunt zijn. Omdat wij die samenwerking niet zochten, kregen we niet de echte data, en lieten we onze berekeningen op kunstmatige data los.”
Daarnaast bleek uiteindelijk ook dat Karp op het verkeerde paard had gewed. De methode van de brute kracht – gebruikt door het bedrijf Celera Genomics van genoomjager Craig Venter – won het van de meer verfijnde methode, waaraan de mensen binnen het publiek gefinancierde genoomproject werkten, en waaraan ook Karp werkte. “We werden ingehaald door een riskantere aanpak dan de onze, die wel degelijk bleek te werken en vooral sneller was in het ontrafelen van het genoom.”
Het ontrafelen van het genoom van een organisme, is voor Karp de belangrijkste bijdrage van de informatica aan de biologie: “Daarvoor moet je een combinatorisch probleem oplossen. Het is alsof je een aantal kopieën van hetzelfde boek in stukken scheurt, de scheursels rondstrooit, en dan aan iemand vraagt om daaruit het oorspronkelijke boek paragraaf voor paragraaf te reconstrueren. Door een combinatie van technologie en slimme algoritmen hebben we dat probleem opgelost. Deze ontwikkeling gaat door, want we willen het genoom steeds sneller en goedkoper ontrafelen.”
De tweede belangrijke bijdrage van de informatica aan de biologie, is voor hem de reconstructie van de evolutionaire levensboom: hoe organismen in de evolutie uit elkaar zijn ontstaan. Karp: “Tot voor kort werd dat gedaan door naar uiterlijke kenmerken te kijken. Die aanpak is grotendeels vervangen door software die met algoritmen de genomen van organismen met elkaar vergelijkt.”
Eiwitinteracties
Dankzij Karps eigen belangrijkste bijdrage aan de bioinformatica, kan zo’n vergelijking tussen organismen nu ook op eiwitniveau. In 2005 publiceerde hij samen met acht collega’s in de Proceedings of the National Academy of Sciences een baanbrekende methode om de netwerken van eiwitinteracties tussen organismen te vergelijken. Ze pasten hun methode toe op de gistbacterie, de fruitvlieg en het wormpje C. elegans.
Karp: “Met ons algoritme konden we een database met meer dan veertienduizend gist-, worm- en fruitvliegeiwitten en bijna veertigduizend bekende eiwitinteracties doorzoeken op overeenkomsten. Zo vonden we netwerken van eiwitinteracties die in alle drie de soorten voorkomen.” Het achterliggende biologische idee hiervan is dat veel eiwitnetwerken in de evolutie bewaard zijn gebleven, terwijl organismen zich van elkaar afsplitsten en zich tot aparte soorten ontwikkelden.
Daarnaast voorspelden de onderzoekers met hetzelfde algoritme dat bepaalde eiwitinteracties moesten bestaan, terwijl biologen deze nog nooit hadden ontdekt. “Meer dan de helft daarvan is daarna wel degelijk gevonden”, zegt Karp. “Dat bewijst dat je met algoritmen interessante eiwitmachinerie kunt opsporen. Ons werk heeft een nieuwe onderzoekslijn in gang gezet die de systeembiologie verder helpt. Bovendien is het een stap in de richting van een computermodel van een cel.” De informatica kan dus echt nieuw inzicht genereren, en is niet alleen maar een hulpwetenschap voor de biologie.
Leeftijdsdiscriminatie
Karp behoort tot de allereerste generatie informatici. Hij studeerde in de jaren vijftig aan de Harvard University af bij het computational lab, nog voordat het huidige vakgebied van de informatica een naam had. Op dat lab voelde hij dat hij deel uitmaakte van een revolutionaire ontwikkeling. “Welk onderzoekspad je ook insloeg, het was allemaal nog onontdekt terrein.” Niet dat hij zich met de computer als apparaat bezig hield, wat misschien voor de hand zou liggen op een computational lab, en in een tijd waarin de computer nog een elitair instrument was. “Ik weet minder van computers dan willekeurig welke informaticus,” zegt Karp, “en waarschijnlijk ook minder dan de meeste tieners.”
Het was vooral de schoonheid van het Hongaarse algoritme dat hem in die tijd de informatica introk. Dit algoritme is de oplossing van het toewijzingsprobleem, waarbij de vraag is hoe je n werknemers het beste aan n werktaken kunt toekennen, zodanig dat de kosten voor de werkgever geminimaliseerd worden. Verder is gegeven welk tarief elke werknemer hanteert voor een bepaalde taak. “Het Hongaarse algoritme gebruikt alleen optellen en aftrekken om dit probleem op te lossen”, vertelt Karp. “Er komt geen vermenigvuldigen of delen aan te pas, dat is het mooie. Als je een algoritme vindt waarbij alles goed werkt, is het als een prachtige machine – een machine in de geest. Het is alsof je als een meubelmaker alle stukken heel precies in elkaar schuift en het meubelstuk er nog prachtig uitziet ook.”
Karp is inmiddels 74 jaar, en nog volop wetenschappelijk actief. In Nederland had hij op zijn 65e al met pensioen moeten gaan, en was hij al jarenlang niet meer toegekomen aan het zelf doen van onderzoek, omdat hij had moeten besturen. Maar Karp wil werken zo lang als hij kan. Hij geeft nog steeds college en begeleidt nog steeds jonge onderzoekers. “Ik ben geen bestuurder”, zegt hij. “Ik ben er nooit voor gevraagd en bovendien ik heb ook geen verstand van geldstromen. Ik zou kunnen zeggen dat mijn doel is om als wetenschapper de mensheid te dienen, maar dat zou niet eerlijk zijn. Natuurlijk vind ik het fijn als mijn algoritmen worden toegepast, maar eerlijk gezegd is mijn grootste drijfveer dat ik veel plezier beleef aan het spelen met wiskundige concepten. Gelukkig is er in de VS geen leeftijdslimiet. Dat is zelfs tegen de wet omdat het leeftijdsdiscriminatie is. 65 is trouwens tegenwoordig helemaal niet zo oud meer.”
Databestanden
Als de natuur rekent, zoals Karp graag zegt, hoe kan het dan dat we van die rekenkundige kant van de biologie vooralsnog weinig terug zien in de biologieleerboeken?
Dat gaat volgens de Amerikaanse informaticus binnen enkele jaren al veranderen. “Realiseer je dat biologen – zeker moleculair biologen – hoe langer hoe meer gebruik maken van grote databestanden die via het internet toegankelijk zijn: informatie over genen en eiwitten. Dat verandert het wezen van het spel. Een bioloog die nu een interessante DNA-volgorde vindt, gaat het internet op en laat een programma zoeken naar vergelijkbare volgorden in andere organismen. Hoe meer we willen weten van hoe een levende cel in detail functioneert, hoe belangrijker deze grote databestanden worden. En ook hoe belangrijker de algoritmen om zinvolle informatie uit die data te halen.”
Staan biologen eigenlijk wel genoeg open voor informatici? Bioloog Leroy Hood, wiens lab in 1986 de eerste semi-automatische DNA-sequencingmachine maakte, heeft gezegd dat informatici niets voor de biologie waard zijn, tenzij ze ook echt het vak biologie leren. Karp glimlacht bij het horen van dit citaat. “Waarschijnlijk dacht hij aan mij toen hij dat zei…Ik heb vier jaar met hem samengewerkt. Maar ik ben het er niet helemaal mee eens. Het hangt af van het type probleem. Het klopt als het bijvoorbeeld gaat om eiwitten. Die hebben een ingewikkelde driedimensionale structuur en een ingewikkelde invloed. Daar moet je inderdaad veel biologische kennis van hebben. Maar het geldt niet als het gaat om DNA. DNA kun je echt zien als een woord in een vierletteralfabet waar je combinatoriek op kunt loslaten. Maar het is zeker nodig om samen te werken met biologen.”
En Karp vindt dat de samenwerking beter wordt. “Wat ik biologen moet nageven, is dat ze niet arrogant zijn, in tegenstelling tot natuurkundigen. Natuurkundigen denken dat ze alles weten. Zij denken dat informatici niets aan hun vak hebben toe te voegen, omdat ze zelf wel weten hoe ze een computerprogramma moeten schrijven. Biologen delen graag wat ze weten en wat ze niet weten. Ik denk dat dat komt omdat er nog zo weinig bekend is over hoe biologie op het systeemniveau van de cel werkt. Biologen weten hoeveel ze nog niet weten.”
[kort profiel] Richard Karp (74) is hoogleraar informatica aan de University of California en aan het International Computer Science Institute, allebei in Berkeley (VS). Karp heeft meerdere belangrijke ontdekkingen op zijn naam staan in de combinatorische algoritmiek en de Operations Research. In 1985 won hij de Turing Award – gezien als de Nobelprijs voor de informatica – voor zijn werk aan een van de grootste onopgeloste problemen uit de wiskunde en de informatica: de vraag of zogenaamde NP-problemen ongelijk zijn aan zogenaamde P-problemen.
P-problemen zijn snel op te lossen. P staat voor die klasse van problemen waarvoor een snelle (polynomiale) oplossingsmethode bestaat, bijvoorbeeld het vinden van de kortste route tussen twee punten op een wegenkaart (dat algoritme zit in een TomTom). Voor NP-problemen is vooralsnog geen snelle oplossing gevonden, maar is een gegeven oplossing wel snel te verifiëren. Het is bijvoorbeeld gemakkelijk te verifiëren dat je 4.294.967.297 kunt ontbinden in de priemfactoren 641 en 6.700.417, want 641 × 6.700.417 = 4.294.967.297, maar er is geen snelle methode bekend om deze priemfactoren te vinden.
Karp bewees in 1972 dat er een bijzondere klasse van NP-problemen bestaat met een gezamenlijk kenmerk. Hiervoor geldt dat als je voor eentje kunt bewijzen dat er een snelle oplossing is, dat ook geldt voor alle andere problemen uit deze klasse. En als je voor eentje kunt bewijzen dat dat niet kan, geldt hetzelfde voor alle andere. Deze klasse van problemen heet NP-volledig.
