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)
Joao Meidanis
Last modified: Sun Apr 19 06:30:40 BRT 2009
by JM