Tao Jiang

Tao Jiang
Professor
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 received B.S. in Computer Science and Technology from the University of Science and Technology of China (USTC) , Hefei, P.R.China in July 1984 and Ph.D. in Computer Science from the University of Minnesota in Nov. 1988. During Jan. 1989 - June 2001, I was a faculty member at Department of Computing and Software, McMaster University, Hamilton, Ontario, Canada. I joined University of California - Riverside as Professor of Computer Science in Sept. 1999, and am a member of the Algorithms and Computational Biology Lab, Genetics Graduate Program, Institute for Integrative Genome Biology, and Center for Plant Cell Biology. I also hold visiting positions at Tsinghua University and Shanghai Center for Bioinformation Technology (SCBIT).

I have published actively in many computer science and bioinformatics/computational biology journals and conferences. For a complete list of my publications, see my CV. Please feel free to send me an email if you would like 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 Computer Science and Technology (JCST) , Journal of Bioinformatics and Computational Biology (JBCB) , BMC Bioinformatics, IEEE/ACM Transactions on Computational Biology and Bioinformatics (TCBB), Algorithmica, and Journal of Computer and System Sciences (JCSS), and program committees of ISMB'08, RECOMB-CG'08, APBC'09, and RECOMB'09. We also helped organize IEEE FOCS'2000 in Redondo Beach, CA, November 12-14, 2000.

Research Interest

Design and analysis of algorithms.
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:
- New Scientist, Nov. 6, 1999, pp. 44-47, "On a Roll" by Dana Mackenzie. More comments on the work can be found here.
- Mathematical Digest, Dec. 1999.
- Courrier International, Dec. 23, 1999 -- Jan. 5, 2000 (#41), pp. 477-478: "Le hasard ne joue pas aux de's", par Dana Mackenzie (translation of the NS article).
- Die Zeit, April 13, 2000 (#16), p. 40: "Geometrisch Eingekreist" by Wolfgang Blum.
Computational molecular biology.
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. Here is the homepage of our software for computing combined DNA and protein alignment (called DPA ). 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 new method for predicting orthologous genes between closely related genomes. This project is currently sponsored by NSF IIS. Your feedback is certainly welcome.
I am presently collaborating with James Borneman, Francey Sladek, and Tim Close. Our research is funded by NSF IIS (joint with Liqing Zhang; see the collaborative project), NSF Plant Genome Research (joint with Tim Close and Stefano Lonardi), and NIH/NLM Biomedical Informatics and Bioinformatics (joint with Jing Li and Tim Chen) programs. Here is an overview of some of the current projects in my lab. We are actively recruiting domestic students to participate in the prestigious NSF IGERT program in Plant Chemical Genomics research.
If you are interested in learning the abc of computational biology and bioinformatics, you may find some useful educational material on the subjects. The DOE Primers on Genomics and Molecular Genetics contain helpful and easy-to-understand information on the Human Genome Project and the field of genomics. 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). A list of the topics covered in the book can be found here. Here is an independent review of the book.
Complexity of finite automata based models.
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.

Teaching

CS 141 : Intermediate Data Structrues and Algorithms, winter quarter, 2008.
CS 238 : Algorithmic Techniques in Computational Biology, spring quarter, 2008. We will examine some fundamental algorithmic topics in computational molecular biology through instructor lecturing, student presentation, and assigned reading and discussion.
CS 150 : The Theory of Automata and Formal Languages, spring quarter, 2008.
CS 260 : Seminar: Selected Topics in Bioinformatics, spring quarter, 2005. This class will mainly consist of student presentations of their own research and interesting work from the current bioinformatics and genomics literature.
Ph.D Depth (Qualifier) Exam : Theory of Computation and Algorithms. You may find a copy of the syllabus of the exam and the 2006 depth exam in PDF format. You can also find many previous comprehensives in Prof. Chrobak's public directory ~marek/PUBLIC. Students who are interested in taking the exam should send Prof. Lonardi or Prof. Chrobak or Prof. Young or me a message as early as possible.
Seminar in Algorithms and Bioinformatics (SAB): a weekly seminar series where students present their research work and interesting papers from recent literature. Its schedule can be found at this page.
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 :-)