[CPM-SPIRE-L] Informatics Distinguished Leverhulme Lecture by Professor Esko Ukkonen at King's College London

[Solon P Pissis]

Dear all,

This is to inform you that on Wednesday 2 December Prof. Esko Ukkonen 
(University of Helsinki) will give a Distinguished Leverhulme Lecture, 
at King's College London, details below.

You are all welcome to attend.

Best regards,
Solon

Speaker: Prof. Esko Ukkonen (University of Helsinki)

Title: DNA Assembly and String Identifiability

When/Where: Wednesday 2 December, 18:30, K3.11

Abstract: The genome assembly problem asks one to reconstruct the DNA 
sequence from the short fragments (called reads) that a sequencing 
instrument samples from the original DNA sequence. The talk describes 
overall architecture of current DNA assembly pipelines and then focusses 
on the exact version of the problem in which the reads are noiseless. 
Given a set F of reads sampled from an unknown target string T, the 
problem is to reconstruct T from F. If T has repeating substrings that 
are longer than the reads, as is often the case for DNA sequences, then 
the reconstruction becomes ambiguous because there may be several 
different reconstructions consistent with the reads. We demonstrate that 
F determines a unique reconstruction, if F is the full k-mer spectrum of 
T and T has no 3-repeats of length k-1 and no interleaved pairs of 
2-repeats of length k-1. A finite-state automaton-like representation of 
the pairwise overlaps of the reads is introduced such that the unique 
identifiability of T reduces to the uniqueness of the Eulerian path in 
this representation.

-- 
Solon P. Pissis

Lecturer in Computer Science (Algorithms & Bioinformatics)
Algorithms and Bioinformatics group
Department of Informatics
King's College London
Strand
London WC2R 2LS
UK

Assistant Managing Editor of the Journal of Discrete Algorithms

Tel:   +44 (0)20 7848 1807 (Office)
        +44 (0)7964 558764  (Mobile)
Skype: solonas13
Email: solon.pissis at kcl.ac.uk
WWW:   http://www.inf.kcl.ac.uk/staff/solon