Seminario Interdipartimentale di Algoritmica
 
 
 

Lunedì 4 Marzo 2002  ore 12:00
Problemi Combinatorici per Polimorfismi di Singoli Nucleotidi
Dr. Giuseppe Lancia
DEI, Università di Padova

Dipartimento di Informatica e Sistemistica - DIS
via Salaria 113, piano secondo
Aula C2

Abstract:
Un polimorfismo e' un tratto che presenta una certa variabilita' in una popolazione (ad es., il gruppo sanguigno nell'uomo). I possibili diversi valori sono detti alleli. A livello di DNA, un polimorfismo e' una regione il cui contenuto varia (in un numero molto limitato di possibilita') in una popolazione. Il piu' piccolo tale polimorfismo consiste di una singola base, che e' presente solo con 2 (fra A,C,T,G) valori, ed e' chiamato SNP (Single Nucleotide Polymorphism, pronunciato "snip"). Il problema dell'Haplotyping consiste nel determinare il valore degli alleli per un insieme di SNPs, a partire dall'output di esperimenti di laboratorio, quali, ad es., piccoli frammenti sequenziati di DNA. A seconda del tipo di dati a disposizione il problema dell'Haplotyping e' stato formalizzato in vari modi come problema combinatorico e/o di ottimizzazione, in anni recenti. In questo talk, vogliamo descrivere tutti questi problemi in un framework unificato, mettendo in risalto i risultati noti e i problemi ancora aperti. In particolare, descriveremo i problemi di:

...dando algoritmi polinomiali per alcuni casi speciali, risultati di NP-completezza e APX-completezza per altri, e algoritmi esponenziali (tipo branch-and-bound) per altri ancora.

Questo lavoro si svolge in collaborazione con Vineet Bafna e Sorin Istrail (Celera Genomics) e Romeo Rizzi (Universita' di Trento)