Dan Gusfield

Gusfield received his undergraduate degree in computer science at the University of California, Berkeley, in 1973,^{[citation needed]} his Master of Science degree in computer science from the University of California, Los Angeles (UCLA), in 1975,^{[citation needed]} and his Ph.D. in engineering science from Berkeley in 1980;^[3] his doctoral advisor was Richard Karp.^[2]

Gusfield joined the faculty at Yale University in Computer Science in 1980, and left in 1986 to join the Department of Computer Science at UC Davis as an associate professor. Gusfield was made Professor of Computer Science in 1992 and served as the chair of the Department of Computer Science at UC Davis from 2000 to 2004. Gusfield was named distinguished professor in 2016, which is the highest campus-wide rank at the University of California at Davis.^[4]

Gusfield's early work was in combinatorial optimization and its real-world application. One of his early major results was in network flow, where he presented a simple technique to convert any network flow algorithm to one that builds the famous Gomory-Hu tree, using only five added lines of pseudo-code.^[5] Another contribution was in stable matching, where he contributed to a polynomial-time algorithm^[6] for the Egalitarian Stable Marriage Problem, proposed by Donald Knuth. Gusfield's work on stable marriage resulted in the book, co-authored with Robert Irving, The Stable Marriage Problem: Structure and Algorithms.^[7] cited over 1500 times in the academic literature.

Starting in 1984, Gusfield branched out into computational biology, making Gusfield one of the first computer scientists to work in this field. His first result in computational biology was written in the Yale Technical Report The Steiner-Tree Problem in Phylogeny. His first published paper in computational biology, "Efficient Algorithms for Inferring Evolutionary History", was published as a technical report in 1988,^[8] and was subsequently published in the journal Networks;^[9] this paper is now the most cited of Gusfield's papers. Gusfield's 1993 paper on multiple sequence alignment^[10] is the first publication indexed in the N.I.H. PubMed under the new term "computational biology".

Gusfield's impact on the early days of Computer Science research in algorithmic computational biology is substantial. His research work was continuously supported by Department of Energy, Human Genome Program; and by the National Science Foundation. He was a member of the United States Department of Energy Human Genome Research Program Panel in 1991, and a member of the steering committee for the Rutgers-Princeton DIMACS center special year on Mathematical Support for Molecular Biology from 1994 to 1995. In 1995, he co-organized the Dagstuhl Conference on Molecular Bioinformatics. He has been a member of the editorial board of the Journal of Computational Biology since its inception in 1996. At the University of California at Davis, he was part of a three-person group that proposed the development of the UC Davis Genomics Center, and served as a member of the Genomics Center Steering Committee (1999–2003), and helped to build an interdisciplinary community of biologists and computer scientists working together on genomics problems. In 2004, Gusfield h proposed the IEEE/ACM Transactions on Computational Biology and Bioinformatics (TCBB), one of the few journals specifically oriented towards computer science and mathematical researchers working in computational biology. He served as its founding editor in chief until 2009,^[11] and later as chair of the TCBB Steering Committee. He was more recently an invited visiting scientist at the Simons Institute for the Theory of Computing at UC Berkeley during two of its semester-long programs (first on Evolution, and later on Algorithmic Challenges in Genomics). In addition, Gusfield has been the PhD advisor or postdoctoral mentor for many well known computer scientists working in combinatorial optimization or computational biology, including Prof. Oliver Eulenstein (Iowa State University),^{[citation needed]} Dr. Paul Horton (Tokyo),^{[citation needed]} Prof. Ming-Yang Kao (Northwestern University),^{[citation needed]} Prof. John Kececioglu (Arizona),^{[citation needed]} Prof. Yun S. Song (UC Berkeley and Univ. of Pennsylvania),^{[citation needed]} Prof. R. Ravi (CMU), Prof. Jens Stoye (Bielefeld), Prof. Lusheng Wang (City University of Hong Kong)^{[citation needed]}, and Prof. Yufeng Wu (U. Connecticut).^{[citation needed]}

Gusfield has made significant contributions to molecular sequence comparison and analysis,^[12] phylogenetic tree and phylogenetic network inference,^[13] haplotyping in DNA sequences,^[14][15][16] the multi-state perfect phylogeny problem using chordal graph theory,^[17] and fast algorithms for RNA folding.^[18] Since 2014 he has focused on the application and development of integer linear programming and the use of Satisfiability Solvers in computational biology.

Gusfield is most well known for his second book Algorithms on Strings, Trees and Sequences: Computer Science and Computational Biology,^[19] which provides a comprehensive presentation of the algorithmic foundations of molecular sequence analysis for computer scientists, and has been cited more than 8400 times in the academic literature.^[1] This book has helped to define and develop the intersection of computer science and computational biology. His third book (the second book in computational biology) is on phylogenetic networks,^[20] which are graph-theoretic models of evolution that go beyond the classical tree model, to address biological processes such as hybridization, recombination, and horizontal gene transfer.

His fourth book (the third book in computational biology) was published in 2019. Integer Linear Programming in Computational and Systems Biology: An Entry-Level Text and Course (Cambridge University Press, 2019. ISBN 9781108421768) explains why and how Integer Linear Programming is a valuable technique for addressing and solving computational problems in biology. It is accompanied by over fifty computer programs that generate the needed inequalities for most of the topics discussed in the book. Subsequently, Gusfield and students explored the use of Satisfiability-solvers to efficiently solve biological problems where integer programming was not effective.

His fifth book was published by Cambridge Press in January 2024. It is entitled Proven Impossible: Elementary Proofs of Profound Impossibility from Arrow, Bell, Chaitin, Gôdel, Turing and more. It presents full, rigorous proofs of deep theorems establishing impossibility in a range of topic areas (in physics, economics, data science, computer science, mathematics, logic) using only arithmetic and simple logic. The presented proofs are built on the simplest, clearest proofs found in the literature, of theorems which originally were considered very difficult and for specialists only. The premise of the book is that more modern proofs of these theorems are much simpler and easier, and when presented for non-specialists, can be understood by anyone with no more than a junior-high education and with the discipline to follow a rigorous logical argument (pen in hand).^{[citation needed]} He is currently finishing writing his sixth book, titled: "The Unique Decipherability Problem: Beauty at the intersection of coding theory, combinatorics, algebra, and algorithms".

Gusfield was named Fellow, the top member designation, limited to one percent of the society members, of three professional societies. He was named Fellow of the Institute of Electrical and Electronics Engineers (IEEE) in 2015^[21] for contributions to combinatorial optimization and computational biology. In 2016, Gusfield was elected a Fellow of the International Society for Computational Biology (ISCB)^[22] 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." He was elected Fellow of Association for Computing Machinery ACM Fellow in 2017.^[23]. Gusfield was named Distinguished Professor, the top faculty rank at UC Davis, in 2016.