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:

• 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)