A  rapidly developing area, computational molecular biology, 
is playing a crucial role in some biological research.  
Our project focuses on the design of efficient and effective 
algorithms for important  combinatorial 
optimization problems arising in  computational 
molecular biology, including 
(1) finding similar regions in many strings, and  
(2) perfect phylogeny with recombination. . 

Finding similar regions in many strings has applications in 
locating binding sites, finding conserved regions in unaligned 
sequences, in genetic drug target identification, etc. Various
 measures have been proposed in different applications. 
Indeed, different ways of measuring errors give different problems  
very different flavors in their complexity and algorithms to solve them. 
We intend to study the following versions: distinguishing substring 
selection, closest string, closest substring, consensus patterns, 
and star c-alignment. All the versions here are NP-hard. 
We propose polynomial time approximation schemes for closest string, 
consensus patterns and c-star alignment. We intend to further study 
and design better (either better ratio or faster algorithm for 
the same ratio) approximation algorithms for all the mentioned problems. 

Perfect phylogeny with recombination is a new model for 
evolutionary history reconstruction We will study this  
problem from algorithmic point of view.

This project will provide a solid theoretical fundation for 
the implementation of the much needed softwares in locating binding sites 
and finding conserved regions in unaligned sequences, in genetic drug 
target identification, in designing genetic probes, in universal PCR primer 
design, and, outside computational biology, in coding theory.