Dan Gusfield

Last updated
Dan Gusfield
Born
Daniel Mier Gusfield
Alma mater University of California, Berkeley (BS, PhD)
Known for Stable marriage problem
Awards
Scientific career
Fields Computer science
Computational biology [1]
Institutions University of California at Davis
Yale University
Thesis Sensitivity analysis for combinatorial optimization  (1980)
Doctoral advisor Richard Karp [2] [3]
Website web.cs.ucdavis.edu/~gusfield

Daniel Mier Gusfield is an American computer scientist, Distinguished Professor of Computer Science at the University of California, Davis. Gusfield is known for his research in combinatorial optimization and computational biology. [1]

Contents

Education

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 PhD in Engineering Science from Berkeley in 1980; [3] his doctoral advisor was Richard Karp. [2]

Career and research

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 a 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]

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, which has never been published in a journal. His first published paper in computational biology, "Efficient Algorithms for Inferring Evolutionary History", was initially published as a technical report in 1988, [8] and was subsequently was 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 PubMed under "computational biology".

Gusfield's impact on the early days of Computer Science research in algorithmic computational biology is substantial. 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. Finally, in 2004, Gusfield helped propose 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 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 in computational biology.

Gusfield is most well known for his 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 8000 times. [1] This book has helped to define and develop the intersection of computer science and computational biology. His 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 third book on 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[ clarification needed ] will be 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 ]

Awards and honors

Gusfield 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." In 2016, Gusfield was named a distinguished professor at the University of California at Davis, which is the highest campus-wide rank. He was elected an ACM Fellow in 2017. [23]

Related Research Articles

<span class="mw-page-title-main">Computational biology</span> Branch of biology

Computational biology refers to the use of data analysis, mathematical modeling and computational simulations to understand biological systems and relationships. An intersection of computer science, biology, and big data, the field also has foundations in applied mathematics, chemistry, and genetics. It differs from biological computing, a subfield of computer engineering which uses bioengineering to build computers.

<span class="mw-page-title-main">Theoretical computer science</span> Subfield of computer science and mathematics

Theoretical computer science (TCS) is a subset of general computer science and mathematics that focuses on mathematical aspects of computer science such as the theory of computation, formal language theory, the lambda calculus and type theory.

<span class="mw-page-title-main">Suffix tree</span> Tree containing all suffixes of a given text

In computer science, a suffix tree is a compressed trie containing all the suffixes of the given text as their keys and positions in the text as their values. Suffix trees allow particularly fast implementations of many important string operations.

<span class="mw-page-title-main">UP Diliman Department of Computer Science</span> Department in College of Engineering in University of the Philippines - Diliman

The Department of Computer Science is one of nine departments in the University of the Philippines Diliman College of Engineering.

In computational phylogenetics, tree alignment is a computational problem concerned with producing multiple sequence alignments, or alignments of three or more sequences of DNA, RNA, or protein. Sequences are arranged into a phylogenetic tree, modeling the evolutionary relationships between species or taxa. The edit distances between sequences are calculated for each of the tree's internal vertices, such that the sum of all edit distances within the tree is minimized. Tree alignment can be accomplished using one of several algorithms with various trade-offs between manageable tree size and computational effort.

<span class="mw-page-title-main">Michael Waterman</span> American mathematician

Michael Spencer Waterman is a Professor of Biology, Mathematics and Computer Science at the University of Southern California (USC), where he holds an Endowed Associates Chair in Biological Sciences, Mathematics and Computer Science. He previously held positions at Los Alamos National Laboratory and Idaho State University.

<span class="mw-page-title-main">International Society for Computational Biology</span> Scholarly society

The International Society for Computational Biology (ISCB) is a scholarly society for researchers in computational biology and bioinformatics. The society was founded in 1997 to provide a stable financial home for the Intelligent Systems for Molecular Biology (ISMB) conference and has grown to become a larger society working towards advancing understanding of living systems through computation and for communicating scientific advances worldwide.

Eugene Leighton (Gene) Lawler was an American computer scientist and a professor of computer science at the University of California, Berkeley.

<span class="mw-page-title-main">Pavel A. Pevzner</span> Russian-born American professor of computational mass spectrometry

Pavel Arkadevich Pevzner is the Ronald R. Taylor Professor of Computer Science and director of the NIH Center for Computational Mass Spectrometry at University of California, San Diego. He serves on the editorial board of PLoS Computational Biology and he is a member of the Genome Institute of Singapore scientific advisory board.

IEEE/ACM Transactions on Computational Biology and Bioinformatics is a bimonthly peer-reviewed scientific journal. It is a joint publication of the IEEE Computer Society, Association for Computing Machinery (ACM), IEEE Computational Intelligence Society (CIS), and the IEEE Engineering in Medicine and Biology Society. It is published in cooperation with the IEEE Control Systems Society.

Bernard M. E. Moret is a Swiss-American computer scientist, an emeritus professor of Computer Science at the École Polytechnique Fédérale de Lausanne in Switzerland. He is known for his work in computational phylogenetics, and in particular for mathematics and methods for computing phylogenetic trees using genome rearrangement events.

<span class="mw-page-title-main">Tandy Warnow</span> American computer scientist (active 1984–)

Tandy Warnow is an American computer scientist and Grainger Distinguished Chair in Engineering at the University of Illinois at Urbana–Champaign. She is known for her work on the reconstruction of evolutionary trees, both in biology and in historical linguistics, and also for multiple sequence alignment methods.

<span class="mw-page-title-main">David Sankoff</span> Canadian scientist

David Sankoff is a Canadian mathematician, bioinformatician, computer scientist and linguist. He holds the Canada Research Chair in Mathematical Genomics in the Mathematics and Statistics Department at the University of Ottawa, and is cross-appointed to the Biology Department and the School of Information Technology and Engineering. He was founding editor of the scientific journal Language Variation and Change (Cambridge) and serves on the editorial boards of a number of bioinformatics, computational biology and linguistics journals. Sankoff is best known for his pioneering contributions in computational linguistics and computational genomics. He is considered to be one of the founders of bioinformatics. In particular, he had a key role in introducing dynamic programming for sequence alignment and other problems in computational biology. In Pavel Pevzner's words, "[ Michael Waterman ] and David Sankoff are responsible for transforming bioinformatics from a ‘stamp collection' of ill-defined problems into a rigorous discipline with important biological applications."

<span class="mw-page-title-main">Ron Shamir</span> Israeli professor of computer science (born 1953)

Ron Shamir is an Israeli professor of computer science known for his work in graph theory and in computational biology. He holds the Raymond and Beverly Sackler Chair in Bioinformatics, and is the founder and former head of the Edmond J. Safra Center for Bioinformatics at Tel Aviv University.

<span class="mw-page-title-main">Ziv Bar-Joseph</span> Israeli computational biologist

Ziv Bar-Joseph is an Israeli computational biologist and Professor in the Computational Biology Department and the Machine Learning Department at the Carnegie Mellon School of Computer Science.

<span class="mw-page-title-main">Gad Landau</span> Israeli computer scientist

Gad Menahem Landau is an Israeli computer scientist noted for his contributions to combinatorial pattern matching and string algorithms and is the founding department chair of the Computer Science Department at the University of Haifa.

<span class="mw-page-title-main">Thomas Lengauer</span>

Thomas Lengauer is a German computer scientist and computational biologist.

<span class="mw-page-title-main">Srinivas Aluru</span>

Srinivas Aluru is a professor in the School of Computational Science and Engineering at Georgia Institute of Technology, and co-Executive Director for the Georgia Tech Interdisciplinary Research Institute in Data Engineering and Science. His main areas of research are high performance computing, data science, bioinformatics and systems biology, combinatorial methods in scientific computing, and string algorithms. Aluru is a Fellow of the American Association for the Advancement of Science (AAAS) and the Institute for Electrical and Electronic Engineers (IEEE). He is best known for his research contributions in parallel algorithms and applications, interdisciplinary research in bioinformatics and computational biology, and particularly the intersection of these two fields.

Mona Singh is a Professor of Computer Science in the Lewis-Sigler Institute for Integrative Genomics at Princeton University.

<span class="mw-page-title-main">Hanah Margalit</span>

Hanah Margalit is a Professor in the faculty of medicine at the Hebrew University of Jerusalem. Her research combines bioinformatics, computational biology and systems biology, specifically in the fields of gene regulation in bacteria and eukaryotes.

References

  1. 1 2 3 Dan Gusfield publications indexed by Google Scholar OOjs UI icon edit-ltr-progressive.svg
  2. 1 2 Dan Gusfield at the Mathematics Genealogy Project OOjs UI icon edit-ltr-progressive.svg
  3. 1 2 Gusfield, Daniel Mier (1980). Sensitivity analysis for combinatorial optimization (PhD thesis). University of California, Berkeley. OCLC   40134251.
  4. ↑ "Dan Gusfield". web.cs.ucdavis.edu. Archived from the original on 17 June 2017. Retrieved 23 January 2019.
  5. ↑ Gusfield. Very Simple Methods for All Pairs Network Flow Analysis. SIAM J. Comput. 1990
  6. ↑ R.W. Irving, P. Leather, and D. Gusfield, "An efficient algorithm for the "optimal" stable marriage", Journal of the ACM, Vol. 34 Issue 3, July 1987, Pages 532-543
  7. ↑ Gusfield, Dan; Irving, Robert (1999). The stable marriage problem: structure and algorithms. MIT Press. ISBN   0-262-07118-5.
  8. ↑ "Computer Science- UC Davis". Cs.ucdavis.edu. 4 October 2018. Retrieved 23 January 2019.
  9. ↑ D. Gusfield, "Efficient algorithms for inferring evolutionary trees", Networks 1991 doi : 10.1002/net.3230210104
  10. ↑ D. Gusfield, "Efficient Methods for Multiple Sequence Alignment with Guaranteed Error Bounds", Bulletin on Mathematical Biology, Vol. 55, No. 1, 141-154, 1993
  11. ↑ Dan Gusfield. "Introduction to the IEEE/ACM Transactions on Computational Biology and Bioinformatics" (PDF). Computer.org. Archived from the original (PDF) on 3 April 2015. Retrieved 23 January 2019.
  12. ↑ Gusfield and J. Stoye. "Linear time algorithms for finding and representing all the tandem repeats in a string", JCSS, 2004
  13. ↑ Gusfield, D., Eddhu, S. and Langley, C., 2004. "Optimal, efficient reconstruction of phylogenetic networks with constrained recombination". Journal of bioinformatics and computational biology, 2(01), pp.173-213.
  14. ↑ Gusfield. "Haploytyping as Perfect Phylogeny: Conceptual framework and efficient solutions." Proceedings of RECOMB 2002.
  15. ↑ Gusfield, D. (2003). "Haplotype inference by pure parsimony." In Combinatorial Pattern Matching (pp. 144-155). Springer Berlin/Heidelberg.
  16. ↑ D. Gusfield, "Inference of haplotypes from samples of diploid populations: complexity and algorithms." Journal of computational biology 8, no. 3 (2001): 305-323.
  17. ↑ Gusfield. "The multi-state perfect phylogeny problem with missing and removable data: solutions via integer linear programming and chordal graph theory." Journal of Computational Biology, 2010.
  18. ↑ Y. Frid and Gusfield. "A simple, practical, and complete -time algorithm for RNA folding using the Four-Russians speedup". Algorithms for Molecular Biology, 2010
  19. ↑ Gusfield, Dan (1999). Algorithms on Strings, Trees and Sequences: Computer Science and Computational Biology. Cambridge University Press. doi:10.1017/CBO9780511574931. ISBN   0-521-58519-8. S2CID   61800864.
  20. ↑ Gusfield, Dan (2014). ReCombinatorics: The Algorithmics of Ancestral Recombination Graphs and Explicit Phylogenetic Networks. MIT Press. ISBN   9780262027526.
  21. ↑ "2015 elevated fellow" (PDF). IEEE Fellows Directory.
  22. ↑ "ISCB Fellows". Iscb.org. Retrieved 23 January 2019.
  23. ↑ ACM Recognizes 2017 Fellows for Making Transformative Contributions and Advancing Technology in the Digital Age, Association for Computing Machinery, December 11, 2017, retrieved 2017-11-13
This page is based on this Wikipedia article
Text is available under the CC BY-SA 4.0 license; additional terms may apply.
Images, videos and audio are available under their respective licenses.