-
Natural sciences
- Parallel programming
- Development of bioinformatics software, tools and databases
-
Engineering and technology
- Bio-informatics
Zoekschema's en een bidirectionele index bieden een nieuw algorithmisch framework voor verliesloze benaderende sequentiealignering. Dit garanteert dat alle benaderend aligneringen gevonden worden. Bijna alle bio-informaticasoftware maakt gebruik van verlieshebbende sequentiealigneringsalgoritmen. Deze zijn historisch sneller dan verliesloze algoritmen. Zoekschema's reduceren dit verschil in performantie tussen beide klassen van algoritmen, en zouden zelfs sneller kunnen zijn. Daarenboven heeft onze onderzoeksgroep reeds prototype software ontwikkeld. Dit prototype bevestigt de verbeterde performantie van zoekschema's. Wij stellen voor om nieuwe verliesloze algoritmen te ontwikkelen voor sequentiealignering, gebruik makende van bidirectionele zoekindexen en zoekschema's door het in rekening brengen van a) de specifieke structuur van de zoektext (herhaalde patronen); b) de eigenschappen van het zoekpatroon. We zullen deze algoritmen primair toepassen op 1) sequentiealignering op een lineair referentie genoom; 2) sequentiealignering voor grafen; 3) sequentiealignering voor lange reads met een hoog foutenpercentage.