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:

- Liliana Alcón, Márcia R. Cerioli, Celina M. H. de
Figueiredo, Marisa Gutierrez and J. Meidanis.
Tree Loop Graphs.
*Discrete Applied Mathematics: The Computational Molecular Biology Series*, accepted for publication, 2005. Download early version - Braga, M. D. V. and J. Meidanis.
An algorithm that builds a set of strings given its overlap
graph.
*Latin American Theoretical Informatics*(LATIN02), Cancun, Mexico, 3-6 April 2002. Download gunzipped ps - Cerqueira, F. R. and J. Meidanis. Algorithms for Large-scale DNA Sequencing. XXVIII Seminário Integrado de Software e Hardware - SEMISH 2001 (This is the main conference in the annual meeting of the Brazilian Computing Society), Fortaleza, Brazil, July/August 2001. Download gunzipped ps. This work was also presented as a 15-minute talk in the RECOMB Satellite Meeting on DNA Sequence Assembly, University of Southern California, May 19 & 20, 2001.
- Lin, Tzy Li. Montagem de Fragmentos de DNA pelo Método "Ordered Shotgun Sequencing" (OSS). (In Portuguese) Msc Thesis, University of Campinas, February 2001. 119 pp. Download zipped ps
- Braga, Marília Dias Vieira. Grafos de Seqüências de DNA. (In Portuguese) Msc Thesis, University of Campinas, December 2000. 119 pp. Download gunzipped ps for: Cover, Rest of Thesis
- Cerqueira, Fábio Ribeiro. Montagem de Fragmentos de DNA. (In Portuguese) Msc Thesis, University of Campinas, January 2000. 70 pp. Download zipped ps
- J. Meidanis.
A Simple Toolkit for DNA Fragment Assembly.
In
*Mathematical Support for Molecular Biology*, M. Farach-Colton, F. S. Roberts, M. Vingron and M. Waterman (Editors), vol. 47 of the DIMACS Series in Discrete Mathematics and Theoretical Computer Science, American Mathematical Society, 1999, pp. 271-288. Download early version (gunzipped ps) - J. Meidanis. Algorithms for Problems in Computational Genetics. PhD Thesis, University of Wisconsin-Madison, 1992. 63 pp. Download gunzipped ps
- Deborah Joseph, Joao Meidanis, and Prasoon Tiwari.
Determining DNA sequence similarity using maximum independent
set algorithms for interval graphs.
In
*Algorithm Theory — SWAT '92*, O. Nurmi, E. Ukkonen (Editors), Proceedings of the Third Scandinavian Workshop on Algorithm Theory, Helsinki, Finland, July 8–10, 1992, vol. 621 of the Lecture Notes in Computer Science Series, Springer, pp. 326-337. Download gunzipped ps (version submitted to J. of Algorithms)

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