UC San Diego

High-throughput techniques in biology have enabled the generation of enormous amount of data allowing researchers to reveal systems level information deciphering the underlying dynamics and mechanisms of the cell. In the last few decades, the immense databases containing DNA, RNA and protein sequences, structures and abundance estimates have been available to researchers. Research in bioinformatics necessitates the use of advanced efficient algorithms to analyze and interpret those biological data. A common characteristic of high-throughput biological data is that it is often incomplete, noisy and inconsistent due to the biases and inefficiencies induced by the laboratory methods. That is why several of the problems defined on biological data can be viewed as constrained optimization problems. In this dissertation, I address different optimization problems that arise in the analysis of biological data: RNA structural alignment, protein interaction network querying, micro-array expression data clustering, protein quantification and protein modification site assignment. The dissertation begins with an overview of the basic concepts of molecular biology and an introduction to the optimization problems to be addressed. Then, each problem is discussed in detail in a separate chapter along with our contribution in the solution of the problem and our results on biological data opening a way for biological discoveries