Projectbeschrijving "Multirelational datamining in bioinformatics", krediet aan navorsers FWO, Jan Ramon
DOEL
Inductief Logisch Programmeren heeft zich in het laatste decennium ontwikkeld tot een goed onderbouwd paradigma voor relationele data mining. De eerste jaren werden vooral algemeen geldige principes en algemeen bruikbare systemen ontwikkeld. Sommige toepassingsdomeinen brengen echter hun eigen specifieke moeilijkheden met zich mee. Domein-specifieke eigenschappen vereisen specifieke methoden en optimalisaties. In dit project willen we Inductief Logisch Programmeren bruikbaarder maken voor een aantal specifieke toepassingsdomeinen. We zullen vooral aandacht besteden aan het domein van de bioinformatica.
CONTEXT
Data mining is het onderzoeksgebied waarin gezocht wordt naar algoritmen om uit een verzameling gegevens interessante informatie (ook patronen of hypothesen genoemd) te halen. Deze informatie kan meer inzicht verschaffen in het domein en/of toelaten voorspellingen te doen over nog onbekende eigenschappen van nieuwe objecten. Een bekend toepassingsdomein is bv. marketing waarbij men de aankopen en gegevens van klanten registreert en dan het aankoopgedrag analyseert en de marketingstrategie daarnaar aanpast.
Inductief Logische Programmeren (ILP) is een paradigma voor data mining waarbij gebruik gemaakt wordt van een eerste orde logica taal om gegevens en hypothesen te beschrijven. Dit heeft als belangrijk voordeel dat men een rijkere taal ter beschikking heeft waarin men relationele patronen kan voorstellen en dus ook complexere verbanden kan ontdekken in gegevensbanken met meerdere relaties. Een ander voordeel is dat men reeds aanwezige domeinkennis gemakkelijk als achtergrondkennis kan toevoegen. Een mogelijk nadeel is dat de grotere zoekruimte een grotere computationele kost meebrengt. Echter, het gebruik van recent ontwikkelde optimalisatietechnieken en de mogelijkheid om de zoekruimte naar de wensen van de gebruiker af te lijnen komen in grote mate tegemoet aan dit probleem.
Bioinformatica is het onderzoeksdomein waarin problemen in de biologie benaderd worden met computationele technieken. Deze methoden zijn zeer belangrijk bij het verkrijgen van meer inzicht en het vinden van nieuwe geneesmiddelen. Twee factoren die data mining een waardevol instrument voor dit domein maken zijn de grootte van de databanken en het grote aantal relaties met verschillende soorten gegevens (structuur en functionaliteit van DNA, structuur en activiteit van molecules, informatie over patienten, abstracten van medische artikels, ...) waarbij men vooral interessante informatie kan bekomen door meerdere informatiebronnen te combineren. Dit is dan ook een typische toepassing waar ILP een meerwaarde heeft. Voorbeelden zijn de analyse van structuur-activiteit relaties (SAR), het zoeken naar patronen in genetisch materiaal, maar ook op een hoger niveau het analyseren van de relatie tussen geneesmiddelen, patientinformatie en de reactie van de patient op de geneesmiddelen.
De nood aan relationele data mining methoden wordt algemeen erkend (cfr. bv. R. Kohavi, uitgenodigd spreker ICML'98). Met de huidige expertise rond machine learning, kennisrepresentatie en efficientie implementatie bevindt DTAI zich in een unieke positie die garant staat voor een internationale rol in dit onderzoek.
Ook het belang van computationele methoden en data mining in de biologie wordt algemeen erkend. De integratie van deze twee domeinen kreeg de naam bioinformatica. De data mining expertise en de goede contacten met experts uit het biomedische domein laat toe deze integratie te verwezenlijken.
PROJECT
Het voorgestelde project wil de bruikbaarheid van ILP in domeinen met grote complexiteit verder verbeteren. We richten ons hierbij in eerste instantie op de bioinformatica, maar de ontwikkelde technieken zullen ruimer bruikbaar zijn. Het project bestaat uit twee componenten: een eerste data mining component waarin aandacht wordt besteed aan het uitbreiden van de data mining algoritmen vanuit de vragen die zich stellen binnen de bioinformatica en een tweede
component waarin geprobeerd zal worden bij te dragen tot het toepassingsdomein (de bioinformatica) door het toepassen van deze algoritmen.
I) Data mining
In de data mining component van het project zal een ILP-systeem ontwikkeld worden dat geoptimaliseerd is voor data mining in bio-medische toepassingen. Er zullen drie onderdelen in meer detail onderzocht worden:
- Afstandsgebaseerde methoden
- Interactie tussen experiment en data mining
- Het verbeteren van de efficientie.
I.1) Afstandsgebaseerde methoden
Meerdere data mining methoden maken gebruik van afstandsfunkties om te meten hoe goed voorbeelden op elkaar lijken. Daarbij veronderstelt men dan dat voorbeelden die goed op elkaar lijken gelijkaardige eigenschappen hebben. Als men bv. een stof kent waarvan men weet dat ze actief is tegen een bepaalde ziekte, dan zal men van stoffen met een gelijkaardige structuur verwachten dat ze meer kans maken om ook actief te zijn tegen die ziekte. In voorafgaand onderzoek werden resultaten gepubliceerd over instantiegebaseerd leren en clustering in eerste orde logica. Het eerste aandachtspunt van de data mining component betreft het verder verfijnen van deze methoden. De integratie van relationele data mining en kernel-gebaseerde methoden en het gebruik van achtergrondkennis zijn hier een belangrijke doelstellingen.
I,2) Interactie tussen experiment en data mining
In een aantal applicaties (o.a. biologie) zijn experimenten en dus ook daaruit resulterende gegevens duur. Daarom is het niet alleen zinvol om zoveel mogelijk informatie uit de beschikbare gegevens te halen maar ook om die experimenten te kiezen die de meest interessante gegevens opleveren. Bij actief leren wordt de normale volgorde van (eerst) gegevens verzamelen en dan analyseren doorbroken. Het leersysteem kan zelf de voorbeelden/experimenten kiezen die het meest informatief zijn en dus best toelaten zijn theorie te verbeteren. Over actief leren werden reeds een aantal resultaten gepubliceerd op een theoretisch niveau(computationele leertheorie) en in toepassingen (o.a. natuurlijke taal). Recent is er ook interesse voor actief leren in bio-medische applicaties. Voor dit onderdeel van het project zal samengewerkt worden met de universiteit van Aberystwyth (Ross King).
I.3) Het verbeteren van de efficientie
Het derde aandachtspunt betreft de efficientie. Data mining algoritmen hebben vaak een hoge computationele kost. Dit geldt vooral voor relationele algoritmen die een grotere zoekruimte hebben. In recent onderzoek werden een aantal optimalisaties ontwikkeld voor bestaande technieken. In het project zullen deze verder verfijnd worden en toegepast worden bij de nieuw ontwikkelde technieken. Deze technieken situeren zich zowel op het lagere niveau van het databanksysteem waarbij de gegevens efficiënt opgevraagd moeten kunnen worden (bv. query-optimalisatie technieken) als op het hogere niveau van de data mining algoritmen (bv. het vermijden van herhalingen van berekeningen en sampling technieken).
II) Bioinformatica
In de bioinformatica component van het project zullen een aantal problemen uit de biologie bestudeerd worden. Daarvoor zal samengewerkt worden met andere onderzoeksgroepen waar data en domeinkennis aanwezig is. Zo is er bv. de samenwerking tussen DTAI, het Rega-instituut van de KUL en de universiteit van Natal ivm. het bepalen van reacties van AIDS patienten op verschillende therapieën (een studieverblijf van een maand in Zuid-Afrika is gepland als onderdeel van dit project). Er zal ook bijgedragen worden tot andere samenwerkingsprojecten met het Rega-Instituut van de KUL, . Tijdens het project zal ook samengewerkt worden met de onderzoeksgroep rond Ross King (universiteit van Aberystwyth (UK)) waar reeds onderzoek gedaan werd naar het gebruik van ILP in functionele genetica en waar interesse is in actief leren.
Door het inpassen van de ontwikkelde technieken in het inductieve kennisbank systeem van de DTAI onderzoeksgroep zullen ze ook gebruikt kunnen worden voor andere toepassingen. Aan de andere kant zal dit toelaten de resultaten van de DTAI groep te gebruiken in dit project. Specifiek voor de bioinformatica denken we daarbij o.a. aan het werk rond kennisrepresentatie en meer bepaald probabilistische voorstellingen van relationele data (hetgeen bv. toelaat om biologische gegevens en resultaten van experimenten nauwkeuriger voor te stellen).