NCBI Computational Biology Branch Seminar     
                  10:00 AM, Friday, January 15, 1999
Conference Room, NCBI, 8th Floor, Building 38A, NLM, NIH, Bethesda MD 20894


Greedy algorithms for optimized DNA sequencing

Allon Percus
Los Alamos National Laboratory 

Abstract 

We discuss the problem of optimally "finishing" a partially sequenced,
reconstructed segment of DNA strand.  While a simplified model may be
solved to optimality by a greedy algorithm, adding more realistic
features appears to make the problem computationally hard.  We suggest
and evaluate a number of near-optimal approaches.  We then propose an
Integer Linear Programming formulation that places it in the context of
more general coverage problems, providing further insight into the
solvability of this important application.


References:   

[1] S. Boettcher and A.G. Percus, "Nature's way of optimizing", 
    submitted to Science.
[2] A.G. Percus and D.C. Torney, "Greedy algorithms for optimized DNA 
sequencing", 
    Proceedings of the 10th Annual ACM-SIAM Symposium on Discrete Algorithms
    (SODA '99), Baltimore, 17-19 January 1999, to appear.