# Dan Gusfield

Dan Gusfield (de nom complet Daniel Mier Gusfield) est un informaticien américain spécialiste en informatique théorique, distinguished professeur emeritus d'informatique à l'université de Californie à Davis. Gusfield est connu pour ses recherches en optimisation combinatoire et en bioinformatique et son ouvrage Algorithms on Strings, Trees, and Sequences.

## Biographie

Gusfield obtient un diplôme de premier cycle en informatique (B. A.) à l'université de Californie à Berkeley en 1973, une maîtrise en informatique (M. S.) de l'université de Californie à Los Angeles en 1975, et un doctorat en sciences (Ph. D.) en ingénierie de l'UC Berkeley en 1980, sous la direction de Richard Karp, avec un thèse intitulée « Sensitivity Analysis for Combinatorial Optimization ». Gusfield rejoint l'université Yale comme professeur assistant en informatique en 1980, puis l'université de Californie à Davis en 1986 en tant que professeur associé en informatique. Il y est professeur d'informatique de 1992 à 2016 ; il est également président du département d'informatique de l'UC Davis de 2000 à 2004. Gusfield est nommé Distinguished Professor en 2016 à l'université de Californie à Davis.
Gusfield a passé deux étés (1988 et 1989) comme chercheur en informatique au Human Genome Center de l'université de Californie à Berkeley, et le semestre d'automne 1994 au centre DIMACS des universités Rutgers et Princeton durant l’année spéciale de biologie moléculaire. En 2014 et en 2016, il est chercheur invité au Simons Institute for Theoretical Computing de l'université de Californie à Berkeley.

## Recherche

Gusfield est surtout connu pour son livre Algorithms on Strings, Trees, and Sequences (Cambridge University Press), qui donne une présentation détaillée des algorithmes fondamentaux intervenant dans l'analyse informatique des séquences. Ce livre a contribué à développer l'interaction entre l'informatique et de la biologie computationnelle. Son deuxième livre en biologie computationnelle est sur les réseaux phylogénétiques.
Les premiers travaux de Gusfield portent sur l'optimisation combinatoire et ses applications. Un de ses premiers résultats majeurs est sur les flots dans les réseaux ; il présente une technique simple pour convertir tout algorithme sur les flots dans les réseaux en un algorithme qui construit également un arbre de Gomory-Hu (en), en ajoutant seulement cinq lignes de pseudo-code. Une autre contribution est un algorithme polynomial pour le problème des mariages stables égalitaires, un problème proposé par Don Knuth. Ce travail de Gusfield a abouti au livre coécrit avec Robert W. Irving.
À partir de 1984, Gusfield travaille en bio-informatique ; il est l’un des pionniers de ce domaine. Sa première publication dans le journal Networks est maintenant le plus cité des articles de Gusfield. L'influence de Gusfield sur la recherche en bio-informatique est considérable dès le début : il a été membre de nombreux comités d'organisation de projets et de colloques, comme la conférence de Dagstuhl sur la bio-informatique moléculaire en 1995. En 2004, Gusfield participe à la création du journal IEEE/ACM Transactions on Computational Biology and Bioinformatics (en) ; il en a été le premier rédacteur en chef et jusqu'en 2009, puis président de son comité de surveillance.
Gusfield a apporté des contributions significatives à la comparaison et à l'analyse de séquences moléculaires, à l'inférence d'arbres et de réseaux phylogénétiques, au haplotypage dans les séquences d'ADN$^,$$^,$, au problème de phylogénie parfaite multi-états utilisant la théorie des graphes chordaux et aux algorithmes rapides pour le repliement de l'ARN. Depuis 2014, il s'intéresse aux applications et au développement de la optimisation linéaire en nombres entiers en biologie computationnelle.

## Honneurs et récompenses

Gusfield est nommé Fellow of the Institute of Electrical and Electronics Engineers (IEEE) en 2015 pour « ses contributions à l'optimisation combinatoire et à la bioinformatique ». En 2016, Gusfield est élu Fellow de l'International Society for Computational Biology pour « ses contributions remarquables à la bio-informatique, en particulier son travail algorithmique sur la construction d'arbres d'évolution, l'analyse de séquences moléculaires, les problèmes de génétique des populations, le pliage d'ARN et la programmation linéaire en biologie ». Il est élu Fellow de l'ACM en 2017.

## Livres

* Dan Gusfield, Algorithms on Strings, Trees, and Sequences : Computer Science and Computational Biology, Cambridge University Press, 1999
* Dan Gusfield et Robert W. Irving, The stable marriage problem : structure and algorithms, MIT Press, 1989
* Dan Gusfield, ReCombinatorics : The Algorithmics of Ancestral Recombination Graphs and Explicit Phylogenetic Networks, MIT Press, 2014
* Dan Gusfield, Integer Linear Programming in Computational and Systems Biology : An Entry-Level Text and Course, Cambridge University Press, 2019, xviii+ 412 (ISBN 978-1-108-37773-7 et 978-1-108-42176-8, zbMATH 1436.92001)