BEGIN:VCALENDAR
VERSION:2.0
PRODID:-//Memento EPFL//
BEGIN:VEVENT
SUMMARY:IPG Seminar: "Decoding Genetic Variations: Communications-Inspired
  Haplotype Assembly"
DTSTART:20141205T141500
DTEND:20141205T151500
DTSTAMP:20260407T064210Z
UID:e828322c0546c38c91a1d200047962b9b3734a33fc19502b5e031f23
CATEGORIES:Conferences - Seminars
DESCRIPTION:Haris Vikalo\, University of Texas at Austin\nHigh-throughput 
 DNA sequencing technologies allow fast and affordable sequencing of indivi
 dual genomes and thus enable unprecedented studies of genetic variations. 
 The complete information about variations in the genome of an individual i
 s provided by haplotypes\, ordered collections of single nucleotide polymo
 rphisms.\nKnowledge of haplotypes is instrumental in finding genes associa
 ted with diseases\, drug development and evolutionary studies\; however\, 
 their reconstruction is computationally challenging (NP-hard). Our key obs
 ervation is that the minimum error-correction formulation of the haplotype
  assembly problem is identical to the task of deciphering a coded message 
 received over a noisy channel – a classical problem in the mature field 
 of communication theory. Exploiting this connection\, we develop novel met
 hods that explore the tradeoffs between performance and complexity of hapl
 otype assembly. Motivated by sphere decoding ideas\, we propose a novel br
 anch-and-bound haplotyping algorithm and find its expected complexity\, de
 monstrating that the optimal haplotype assembly\, often considered impract
 ical\, is in fact practically feasible for haplotype blocks of moderate le
 ngth. For long haplotype blocks\, we reformulate the problem as a semi-def
 inite program and exploit its structural features to derive a fast and acc
 urate heuristic solution. Finally\, an information-theoretic analysis of h
 aplotype assembly allows us to establish its fundamental\nperformance limi
 ts.
LOCATION:INR113 http://plan.epfl.ch/?zoom=20&recenter_y=5863814.94355&rece
 nter_x=730548.85489&layerNodes=fonds\,batiments\,labels\,information\,park
 ings_publics\,arrets_metro\,transports_publics&floor=1&q=inr113
STATUS:CONFIRMED
END:VEVENT
END:VCALENDAR