Fragment Assembly

In large-scale DNA sequencing we are given a collection of many, many fragments (short DNA sequences) which are approximate substrings of a very long DNA molecule. The problem known as fragment assembly is to reconstruct the original sequence from the fragments.

I have been interested in these problems since 1990, when I was a PhD student at the University of Wisconsin, USA. Many students of mine have worked on the problem, some from a theoretical point of view, others from a practical point of view.

In the last years, my colleagues Celina Figueiredo, Marisa Gutierrez, Liliana Alcon and Marcia Cerioli got interested in the problem, and we started studying a novel approach which is to relate fragment assembly with a certain class of graphs, the interval graphs with repeats, with the goal of modeling the repeats that often appear in DNA sequences. Loop graphs are a special case of interval graphs with repeats. This research can also be applied to physical mapping.

Here are some of our papers on the subject:

Joao Meidanis
Last modified: Sun Apr 19 06:30:40 BRT 2009 by JM