Short Biosketch August 2016
Dan Gusfield
General:
My background is in Combinatorial Optimization, and various
applications of Combinatorial Optimization. I have worked extensively
on problems of network flow, matroid optimization, statistical data
security, stable marriage and matching, string algorithms and sequence
analysis, phylogenetic tree inference, haplotype inference, inference
of phylogenetic networks with homoplasy and recombination, and the
multi-state perfect phylogeny problem, using chordal graph theory and
integer programming.
I received my Ph.D. in 1980 from UC Berkeley, working with Richard
Karp, and was an Assistant Professor at Yale University from 1980 to
1986. My dissertation concerned problems of sensitivity analysis
in graphs, network flow and Matroid
theory. I moved to UC Davis in January 1987. In July 2016, I was
promoted to the rank of Distinguished Professor.
My interest in the Stable
Marriage Problem resulted in the publication of the book "The
Stable Marriage Problem: Structure and Algorithms" (MIT press, 1988),
co-authored with Rob Irving. Since then, I have mostly addressed
problems in Computational Biology and Bioinformatics. I first
addressed questions about building evolutionary trees, and then
problems in molecular sequence analysis. I presently focus mostly on
optimization problems related to population genetics and
population-scale genomics. Three particular problems are haplotype
inference, inferences about historical recombination, and the
multi-state perfect phylogeny problem. Another area of research is
the development of efficient algorithms for RNA folding, particularly developing
methods based on the Four-Russians idea. A secondary general theme of my
work is the
development and use of integer linear programming to solve practical problem
instances of problems in computational biology. My main funding for
computational biology and bioinformatics came initially from the
Department of Energy Human Genome Project through the Lawrence Berkeley
Labs Human Genome Center, then directly from DOE Human Genome Project,
but since then, my work in computational biology has been funded by the
NSF, in the IIS, ITR and CCF programs. In their spring semesters 2014 and 2016, I was an
(invited, supported) visiting scientest at the Simons Institute for Theoretical
Computing at UC Berkeley, and was previously a long-term (invited, supported)
visitor at the DIMACS Center for Theoretical Computer Science at Rutgers/Princeton;
and at the Isaac Netwon Centre for Mathematics, Cambridge University.
My book, ``Algorithms on Strings,
Trees and Sequences: Computer Science and Computational Biology"
(Cambridge Press, 1997) has helped to define the intersection of
computer science and computational biology. I have also authored the
book ``ReCombinatorics: The Algorithmics of Ancestral Recombination Graphs and Explicit
Phylogenetic Networks", which was published by MIT Press in July 2014.
Major Professional Service:
I wrote the scientific section of the
proposal to create the IEEE/ACM Transaction on Computational Biology
and Bioinformatics (www.computer.org/tcbb/), and served as the
journal's founding Editor-in-Chief for five years. I was later chair
the Steering Committee for the journal. I serve on the editorial
board of the Journal of Computational Biology, and served on the editorial board of the
SIAM J. on Computing. I have served on many NSF and DOE
research-proposal panels on computer science, bioinformatics and
computational biology, and on numerous conference program committees. I
co-chaired the program committee for the 1994 conference on
Combinatorial Pattern Matching; I co-organized the 1995 Dagstuhl
Conference on Bioinformatics at the Dagstuhl Center in Germany; I
co-chaired the program committee of the 2002 Workshop on Algorithms for
Bioinformatics (WABI) held in Rome; I was the Program Chair of the 2004
RECOMB (Research on Computational Molecular Biology) conference in San
Diego; and was the Proceedings Chair of the ISMB (Intelligent Systems in Molecular Biology)
2009 Conference in Stockholm. In fall 2014 I served on the Committee of Visitors for the
four-year review of the CISE directorate of the NSF. In 2015 I was elevated to the rank of Fellow of the IEEE
(Institute for Electrical and Electronics Engineers) with the citation:
For contributions to combinatorial optimization and computational biology. In 2015 I was won the College of Engineering
Deans award for the Outstanding Senior Faculty Member. In 2016 I was made Fellow of ISCB (International Society of
Computational Biology) with the citation: For his notable contributions to computational biology, particularly his algorithmic work on building evolutionary trees, molecular sequence analysis, optimization problems in population genetics, RNA folding, and integer programming in biology.
Major UC Davis Service:
At UC Davis I was chair of the
Computer Science Department for four years. I wrote the
bioinformatics section (one of three) of the Genomics/Bioinformatics
initiative proposal that resulted in the creation of the UCD Genomics
Center (which hired 17 new faculty), and I served on the steering
committee of the Genome Center, and committees for center faculty
hiring in bioinformatics. I was co-chair of the UCD campus initiative
on ``Computational Characterization and Exploitation of Biological
Networks", which hired seven new faculty in seven different
departments. I was the College of Engineering faculty chair for one year,
and served on the College of Engineering Faculty Personnel Committee.
I also served for more than three years on Committee on Academic Personnel (CAP) for the campus.
Major Educational Efforts:
I developed and taught
an undergraduate course on the Theory and Practice of Bioinformatics
taught mostly to biology students, and a graduate course on Sequence
Analysis and Computational Biology, taught mostly to computer science
and mathematics students. I have videos of about 30 hours of my lectures on
topics in bioinformatics, posted on my website. These have been edited for
distribution on ItunesUniversity, and should appear there shortly.
In the area of computer
science theory, I teach both the undergraduate and graduate courses on Algorithms,
and have recorded and edited more than 70 hours of videos of my lectures
on undergraduate and graduate courses on Design and Analysis of Algorithms,
and another 24 hours of lectures on Theory of Computation. I recently made and
posted two video lectures, and a writeup, on Godel's (first) incompleteness theorem.
The lectures present
a streamlined, yet rigorous, proof of the theorem requiring minimal
background (you don't have to speak German or ponder the meaning of "truth" to understand the proof).
I gave those lectures in my first classes in the
undergraduate course on Theory of Computation in fall 2014. More recently, I made and posted four
hours of lectures on the Fast Fourier Transform, the most important algorithm that computer science
students don't regularly learn. I am now editing
videos for a course on Combinatorial Optimization which will be posted on ItuneU.
Most of the videos are also available through my website, and some are posted on
Youtube.