Department of Computer Science and Engineering
University of California - Riverside
Riverside, CA 92521
lastname AT cs DOT ucr DOT edu
Phone: (951) 827-2991
Fax: (951) 827-4643
Office: Engineering Building II, Room 336
I have published actively in many computer science and bioinformatics/computational biology journals and conferences. For a complete list of my publications and other info, please see my CV or short biography. Please feel free to send me an email if you would like to receive an up-to-date version of any of the papers (electronically or in hardcopy). You will be guaranteed to receive a prompt response (unless I am on the road).
I am presently serving on the editorial boards of Journal of Combinatorial Optimization (JCO) , Journal of Bioinformatics and Computational Biology (JBCB) , BMC Bioinformatics, Algorithmica, and Journal of Computer and System Sciences (JCSS), and program committees of RECOMB-Seq'2013 and MFCS'2013.
We study discrete objects such as strings, trees, graphs, etc., and have a special interest in the design of efficient approximation algorithms with good performance bounds. Our recent work includes approximation algorithms for shortest common superstrings and directed Steiner trees. We are also working on an average-case analysis technique based on the incompressibility method, which involves the theory of Kolmogorov complexity. Our recent results incldue average-case analyses of algorithms for a wide range of problems including sorting, majority, matrix multiplication, random walk, communication complexity, and problems in geometry.
Our result on the average size of Heilbronn's triangles has been featured/reported in popular science magazines and newspapers:
We are interested in developing efficient algorithms and software for computational problems in molecular biology and genomics. Our recent work includes efficient algorithms for comparison of annotated sequences, comparative plant/bacterial genomics, probe set design and cluster analysis for oligonucleotide fingerprinting of ribosomal RNA genes (OFRG), search for transcription factor binding sites, NMR peak assignment (see the article "NMR and the 3D World of Proteins" in RSC Chemstry World citing our work), haplotype inference on pedigrees, genome-scale ortholog assignment, and a few prototype software tools. PedPhase is a suite of programs for inferring haplotypes from genotypes on a pedigree. TISHunter is a web server for predicting translation initiation sites in eukaryotic mRNAs using a support vector machine. W-AlignAce is a web server for discovering motifs from sequence and expression (or ChIP-chip) data. MSOAR is a method for predicting orthologous genes between closely related genomes that takes gene order into consideration. The project was sponsored by NSF IIS. IsoLasso is a combinatorial approach for inferring mRNA isoforms and their expression levels from RNA-Seq data.
I am presently collaborating with James Borneman, Frances Sladek, and Thomas Girke. Our research was/is funded by NSF IIS (joint with Liqing Zhang; see the collaborative project), NIH NIDDK (joint with Frances Sladek), NIH Innovations in Biomedical Computational Science and Technology (joint with James Borneman, Marek Chrobak, Xinping Cui, and Dan Jeske), and NIH/NLM Biomedical Informatics and Bioinformatics (joint with Jing Li and Tim Chen; see also the renewal) programs. Here is a (somewhat outdated) overview of some of the projects in my lab.
If you are interested in learning the abc of computational biology and bioinformatics, you may find some useful educational material on the subject (in particular, A Primer on Molecular Genetics). Our book Current Topics in Computational Molecular Biology was published by the MIT Press as a part of its Computational Molecular Biology Series (and co-published by Tsinghua Univ. Press in China) although the topics covered in the book are probably no longer current in the field :-)
We are mostly interested in the following long-standing open problems: (i) succinctness of two-way (nondeterministic and deterministic) finite automata and (ii) connectivity in digital images and 2-dimensional finite automata. Kolmogorov complexity has been the main technique in my recent work on related problems.
Here is one of the top 5 Othello programs done by students in my data structures and algorithms class as their programming project in 1997. The program is written in Java, by M. Plug, D. Willits, and B. Vujic. See if you can beat it :-)