Tao Jiang Professor Department of Computer Science and Engineering University of California - Riverside Riverside, CA 92521 jiang AT cs DOT ucr DOT edu Phone: (951) 827-2991 Fax: (951) 827-4643 Office: Surge Building, Room 330

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 International Journal of Foundations of Computer Science (IJFCS) , Journal of Combinatorial Optimization (JOCO) , 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), and Algorithmica, and program committees of FCT'2005, RECOMB'2005, and ISMB'2005. 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, quartet-based reconstruction of evolutionary trees, 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, haplotyping on pedigrees, and a few prototype software tools. From this page, you can download our integrated multiple sequence alignment and phylogenetic reconstruction system on X-Windows (called TAAR V1.0 ). 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. Your feedback is certainly welcome.

  I am presently collaborating with Ming Li, Mike Clegg, James Borneman, Francey Sladek, Ying Xu, and Tim Close. Our research is funded by NSF CCF, NSF ITR (see also the ITR collaborative award), NSF DBI, DOE Genomes to Life, and NSF Plant Genome programs. Here is an overview of the current 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 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 has recently been 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

This year I am teaching two undergraduate courses, a graduate course, and a graduate seminar:
• CS 150 : The Theory of Automata and Formal Languages, fall quarter, 2004, and winter quarter, 2005.
• CS 238 : Algorithmic Techniques in Computational Biology, spring quarter, 2005. We will examine some fundamental algorithmic topics in computational molecular biology through instructor lecturing, student presentation, and assigned reading and discussion.

• CS 260 : Seminar: Selected Topics in Bioinformatics, Spring, 2005.

• Ph.D Depth (Qualifier) Exam : Theory of Computation and Algorithms. You may find a copy of the syllabus of the exam and the 2003 Summer Comprehensive 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 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 :-)

My office hours

Past Postdocs and Ph.D Students