PhD defense Michaël Vyverman: ALFALFA: Fast and Accurate Mapping of Long Next Generation Sequencing Reads

Dec
05
Dec/05 17:30
UGent, campus sterre, gebouw S9, Multimediazaal, Krijgslaan 281, 9000 Gent
When: 
Friday, December 5, 2014 - 17:30
Where: 

UGent, campus sterre, gebouw S9, Multimediazaal, Krijgslaan 281, 9000 Gent

(The defense will be in Dutch)

Het bepalen van het volledige genoom van een organisme (genoomsequenering) is een van de hoekstenen van de bioinformatica. Onderzoekers zijn momenteel nog niet in staat om de nucleotiden van een genoom in één keer te bepalen. In plaats daarvan doen ze een beroep op hoogtechnologische chemische methoden (next-generation sequencing) om de nucleotidenvolgorde te bepalen van korte stukjes DNA. Deze korte stukjes worden reads genoemd.
Het aligneren van reads (read mapping) vormt een belangrijke stap bij het hersequeneren. Wanneer de volledige genoomsequentie van een organisme gekend is, kan deze als referentiesequentie gebruikt worden om genetische variatie in kaart te brengen. Hiervoor worden reads uitgelezen van aanverwante organismen om daarmee de verschillen ten opzichte van de referentiesequentie te bepalen. Om het DNA van een organisme te vergelijken met zijn referentiesequentie, moet voor elke read de corresponderende positie op de referentiesequentie bepaald worden. Dit noemt men het mappen van de reads op de referentiesequentie.
Op basis van deze informatie kan dan gezocht worden naar genetische variaties binnen een populatie. Zo bestaan ongeveer 90% van alle variaties in het menselijke genoom uit enkelvoudige mutaties (single-nucleotide polymorphisms, SNP's). Tegenwoordig wordt geschat dat een mens op elke 1300 nucleotiden in zijn DNA een SNP heeft. Dat zijn zo'n vijf miljoen SNP's verspreid over het hele menselijke genoom. De meeste van die genetische variaties zijn vermoedelijk onschuldig, maar sommige ervan werden geassocieerd met erfelijke aandoeningen zoals een verhoogd risico op de ziekte van Alzheimer.
Read mapping staat echter voor een aantal belangrijke algoritmische uitdagingen:
i) de korte reads bevatten geen richtingaanwijzers: we weten niet uit welk deel van het genoom ze afkomstig zijn; we moeten dus de sequentie van de read gebruiken om de overeenkomstige regio in de referentiesequentie te vinden,
ii) de referentiesequentie kan vrij lang zijn (ongeveer drie miljard nucleotiden in het menselijk genoom), waardoor het vinden van een overeenkomstige regio geen eenvoudige opgave is,
iii) delen van de referentiesequentie kunnen zeer sterk op elkaar gelijken en geven ongeveer dezelfde kans dat de read daar werd uitgelezen (bijvoorbeeld in repetitieve regio's),
iv) als we enkel zoeken naar perfecte overeenkomsten met de referentiesequentie dan vinden we nooit natuurlijke variatie; daarom moeten we een paar fouten in de reads toelaten,
en v) ondanks het feit dat genoomsequenering vandaag de dag is uitgegroeid tot een miljardenbusiness, blijven sequeneringsmachines die de reads identificeren nog steeds in een substantieel aantal gevallen fouten produceren; analoog aan de natuurlijke variatie, moeten we dus rekening houden met een klein aantal sequeneringsfouten in de reads en deze later proberen te onderscheiden van de natuurlijke variatie.
Bovendien geldt ook hier het Olympische motto citius, altius, fortius (sneller, hoger, sterker) omdat dit alles moet gebeuren voor miljoenen reads, en dit liefst zo snel mogelijk, met zo weinig mogelijk geheugen en zo nauwkeurig mogelijk. In dit proefschrift introduceren we daarom nieuwe indexstructuren en algoritmen die kunnen ingezet worden om het read mapping probleem aan te pakken, samen met de implementatie van een snelle, geheugenvriendelijke en betrouwbare read mapper: het softwarepakket ALFALFA (A Long Fragment Aligner/A Long Fragment Aligner).

Tags: 
Event type: