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: Winston Chung Hall (WCH), Room 336
For a complete list of my publications and other detailed info, please see my Google Scholar page or CV or short biography. I am presently serving on the editorial boards of Journal of Combinatorial Optimization (JCO) , BMC Bioinformatics and Algorithmica, and program committees of RECOMB'2023 and ISMB'2022.
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 past work includes approximation algorithms for shortest common superstrings and directed Steiner trees. We have also worked on an average-case analysis technique based on the incompressibility method, which involves the theory of Kolmogorov complexity. Our result on the average size of Heilbronn's triangles was featured/reported in popular science magazines and newspapers:
Our lower bound on the average-case complexity of the well-known Shellsort algorithm is mentioned on this wiki page, and still remains as the best!
We are interested in developing efficient algorithms and software for computational problems in molecular biology and genomics. Our past work includes efficient algorithms for haplotype inference on pedigrees, genome-scale ortholog assignment, isoform inference, metagenomics, and isoform-based differential analysis. 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. MSOAR is a method for predicting orthologous genes between closely related genomes that takes gene order into consideration (see the Github page for source code). 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 Frances Sladek, Thomas Girke, and James Borneman. Our research is/was funded by NSF EAGER, 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 :-)
The following are two examples of long-standing open problems that we are interested in: (i) succinctness of two-way (nondeterministic and deterministic) finite automata and (ii) detection of connectivity in digital images by 2-dimensional finite automata. Kolmogorov complexity has been the main tool in our past work on similar problems.