Monday, April 16, 2012

[DMANET] Postdoc on distance geometry and bioinformatics at LIX, Ecole Polytechnique

Postdoctoral fellowship "Distance geometry and molecular structure"

- Leo Liberti, LIX Ecole Polytechnique, France.
- Carlile Lavor, IMECC UNICAMP, Brazil.
- Antonio Mucherino, IRISA Univ. of Rennes I.

April 4, 2012

A postdoctoral position for 21 months (structured in a first
"probationary" 9 months period renewable for another full year),
financed by the French national research agency ANR through the
"Bip:Bip" project ("health and biotechnologies" action) will open at
LIX, Ecole Polytechnique, from September 2012. The "Bip:Bip" project
is a large-scale multi-partner bio-informatics project coordinated by
Institut Pasteur (Dr. M. Nilges). LIX is responsible for a
work-package about the application of distance geometry based methods
to the determination of the spatial structure of macromolecules.

>From a mathematical point of view, the fundamental problem being
solved is that of finding a set of points in 3D space that match a
sparse set of inter-point Euclidean distances. From a biological point
of view, several factors complicate the situation: the distances are
actually Nuclear Magnetic Resonance (NMR) measurements, and as such
they are subject to errors; furthermore, NMR experiments can only
provide distances to up to a threshold, and are only accurate on
certain types of atoms (e.g. hydrogens). Besides, more information
about the molecules can be exploited besides NMR data.

In the past, we have been working on mixed-combinatorial distance
geometry methods for realizing proteins from NMR data, focusing on a
simple but effective algorithm known as Branch-and-Prune (BP). We
developed a rich mathematical theory spanning, among other topics,
theoretical complexity of the associated formal problems, symmetry
analysis by partial reflection groups, and a detailed worst-case
complexity of the BP algorithm on proteins. We contributed a very
efficient open-source implementation thereof (called MD-jeep), and are
working on parallel versions. We are able to cater for typical
biological constraints (distance errors and increased accuracy for
hydrogen atoms). We are currently extending the BP to work with other
molecular information besides distances.

The objective of this postdoc is to interact with researchers at
Institut Pasteur, and the other partners of the Bip:Bip project, in
order to adapt the BP to solve open problems in proteomics, with a
specific attention to the determination of the structure of
macromolecules. This might mean extending BP's capabilities, as well
as complementing the BP algorithm with existing methodologies of a
different type (e.g. SDP-based graph decomposition methods, such as
the facial reduction algorithm or the very recent 3D-ASAP method).
Most of all, it will mean interfacing with the biologists to
understand their requirements and formalize them in such a way that it
is acceptable to them. Ultimately, this research should lead to
computationally efficient algorithms for the problems being solved.

The successful candidate should be: an accomplished mathematician,
versed in distance geometry; a good computer scientist who understands
the theory of algorithms and complexity; an excellent implementor, who
can code in C/C++ on a variety of platforms; and a good
bioinformatician. Although we'd love to have an "and" between all
these qualities, we'll settle for the best combination of "and" and

The precise salary is difficult to evaluate. We have access to the
figure ANR will spend (4333EUR), but this also pays for benefits,
taxes on the employer's side, taxes on the employee's side, and
revenue tax, which depends on the individual situation.
Experience tells us that the worst case for the net salary, after all
tax, is in the range 2000-2200EUR/month.

If you are interested, and either you already have a Ph.D. degree in
mathematics, computer science, engineering or bioinformatics, or are
going to obtain one by or around september 2012, please send
application material as detailed below to Leo Liberti
( in PDF format *only*.
1. A motivation letter explaining how you fit the postdoc position
description and why.
2. A detailed CV, including a complete list of publications (long CVs
are OK).
3. A PDF copy of your Ph.D. thesis (or draft).
4. PDF copies of those paper of yours that you feel most appropriate to
this position (no more than three please).
5. PDF scans of recommendation letters (no more than five please).

We shall evaluate applications at the end of each calendar month until
the position is filled.

Leo Liberti
Carlile Lavor
Antonio Mucherino
* Contributions to be spread via DMANET are submitted to
* Replies to a message carried on DMANET should NOT be
* addressed to DMANET but to the original sender. The
* original sender, however, is invited to prepare an
* update of the replies received and to communicate it
* via DMANET.