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) , BMC Bioinformatics and Algorithmica, and program committees of RECOMB'2016 and ISMB'2016.
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 haplotype inference on pedigrees, genome-scale ortholog assignment, isoform inference, and metagenomics. 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. IsoLasso is a combinatorial approach for inferring mRNA isoforms and their expression levels from RNA-Seq data. See the feature article in Genetic Engineering and Biotechnology News mentioning our work on isoform inference and differential expression analysis.
I am presently collaborating with James Borneman, Frances Sladek, and Thomas Girke. Our research is/was funded by NSF ABI (joint with Grace Xiao at UCLA; see the collaborative project) and NIH NIDDK (joint with Frances Sladek), 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 :-)