pop up description layer
 

PRE-Class
S.R. Eddy: What is dp?
(3.2'21 update) voordracht (pdf)

Pavel Pevzner The Manhattan Tourist Problem (youtube)

Catalan Numbers
(Smiling Faces, Hand Shaking Problem)
Sloane on-line encyclopedia

In het kader van PRE-classes», voorheen LAPP-Top, een college over algoritmische problemen in de bio-informatica, meer precies computational molecular biology. Het thema is dynamisch programmeren, een techniek waarbij een probleem opgelost wordt door deelproblemen eerst uit te werken en daar de oplossingen van in een tabel op te slaan en later te gebruiken.

We hebben het probleem van de Bavarian Beer Party geanalyseerd, zoals gegeven op een recente programmeerwedstrijd (zie de versie uit China). Dit lijkt een speeltje, maar is een vereenvoudigde versie van het probleem om de structuur van RNA te bepalen. Verder hebben we gekeken naar alignment, een methode om uit te rekenen hoeveel twee strings DNA op elkaar lijken. Dit is een andere toepassing van dynamisch programmeren. Helaas zijn de DNA databanken zo groot geworden dat zelfs deze snelle methode niet voldoet. Er worden heuristieken gebruikt: methoden die een goed antwoord geven, maar niet altijd het beste. Voor DNA matches in de centrale databases voor het genoomonderzoek is dat BLAST.

RNA secondary structure dynamisch programmeren
(29.1'09) opdracht: excel

wiki: cellulaire automaat

Tom van der Zanden (LAPP-Top 2009)
1D Cellulaire Automaat (in javascript)

Prakticum. Na het 'college' gedeelte kan alignment uitgerekend worden met excel, of voor diegenen die al kunnen programmeren in hun favoriete taal. Als toetje worden ook patronen gegenereerd in excel, de zgn. cellulaire automaten.
up up2