Dan Gusfield

Données clés
Domaines	Informatique théorique, Bio-informatique
Institutions	Université de Californie à Davis, Université Yale
Formation	Université de Californie à Berkeley
Directeur de thèse	Richard Karp
Renommé pour	Algorithms on Strings, Trees, and Sequences
Distinctions	IEEE Fellow (2015); ISCB Fellow (2016); ACM Fellow (2017);
Site	http://web.cs.ucdavis.edu/~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 »^[1]. 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^[2].

Gusfield a passé deux étés (1988 et 1989) comme chercheur en informatique au Human Genome Center de l'université de Californie à Berkeley^[3], 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^[4] (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^[5].

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^[6]. Une autre contribution est un algorithme polynomial pour le problème des mariages stables égalitaires, un problème proposé par Don Knuth^[7]. Ce travail de Gusfield a abouti au livre coécrit avec Robert W. Irving^[8].

À 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^[9] 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^[10], puis président de son comité de surveillance.

Gusfield a apporté des contributions significatives à la comparaison et à l'analyse de séquences moléculaires^[11], à l'inférence d'arbres et de réseaux phylogénétiques^[12], au haplotypage dans les séquences d'ADN^[13]^,^[14]^,^[15], au problème de phylogénie parfaite multi-états utilisant la théorie des graphes chordaux^[16] et aux algorithmes rapides pour le repliement de l'ARN^[17]. 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^[18] pour « ses contributions à l'optimisation combinatoire et à la bioinformatique ». En 2016, Gusfield est élu Fellow de l'International Society for Computational Biology^[19] 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^[20].

Livres

Dan Gusfield, Algorithms on Strings, Trees, and Sequences : Computer Science and Computational Biology, Cambridge University Press, 1999^[21]
Dan Gusfield et Robert W. Irving, The stable marriage problem : structure and algorithms, MIT Press, 1989^[22]
Dan Gusfield, ReCombinatorics : The Algorithmics of Ancestral Recombination Graphs and Explicit Phylogenetic Networks, MIT Press, 2014^[23]
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)

Notes et références

(en) Cet article est partiellement ou en totalité issu de l’article de Wikipédia en anglais intitulé « Dan Gusfield » (voir la liste des auteurs).

↑ (en) « Daniel Mier Gusfield », sur le site du Mathematics Genealogy Project.
↑ Page personnelle de Gusfield.
↑ Dan Gusfield - un brève autobiographie.
↑ Algorithms on Strings, Trees, and Sequences.
↑ Gusfield 2014.
↑ Dan Gusfield, « Very Simple Methods for All Pairs Network Flow Analysis », SIAM J. Comput, vol. 19, n^o 1,‎ 1990, p. 143-155.
↑ Robert W. Irving, Paul Leather et Dan Gusfield, « An efficient algorithm for the "optimal" stable marriage », Journal of the ACM, vol. 34, n^o 3,‎ 1987, p. 532-543.
↑ Gusfield et Irving 1989.
↑ Dan Gusfield, « Efficient algorithms for inferring evolutionary trees », Networks, vol. 21, n^o 1,‎ 1991, p. 19–28 (ISSN 0028-3045, DOI 10.1002/net.3230210104)
↑ Transactions on Computational Biology and Bioinformatics : Introduction.
↑ Dan Gusfield et Jens Stoye, « Linear time algorithms for finding and representing all the tandem repeats in a string », J. Comput. Syst. Sci., vol. 69, n^o 4,‎ 2004, p. 525-546.
↑ Dan Gusfield, Satish Eddhu et Charles H. Langley, « Optimal, Efficient Reconstruction of Phylogenetic Networks with Constrained Recombination », J. Bioinformatics and Computational Biology, vol. 2, n^o 1,‎ 2004, p. 173-214.
↑ Dan Gusfield, « Haploytyping as Perfect Phylogeny: Conceptual framework and efficient solutions », Proceedings of RECOMB,‎ 2002, p. 166-175.
↑ Dan Gusfield, « Haplotype inference by pure parsimony », dans Combinatorial Pattern Matching, Springer Verlag, 2003, p. 144-155.
↑ Dan Gusfield, « Inference of Haplotypes from Samples of Diploid Populations: Complexity and Algorithms », Journal of Computational Biology, vol. 8, n^o 3,‎ 2001, p. 305-323.
↑ Dan Gusfield, « The Multi-State Perfect Phylogeny Problem with Missing and Removable Data: Solutions via Integer-Programming and Chordal Graph Theory », Journal of Computational Biology, vol. 17, n^o 3,‎ 2010, p. 383-399.
↑ Yelena Frid et Dan Gusfield, « A simple, practical and complete $O(n^{3}\log n)$ -time Algorithm for RNA folding using the Four-Russians Speedup », Algorithms for Molecular Biology, vol. 5,‎ 2010, article n^o 13 (DOI 10.1186/1748-7188-5-13).
↑ « 2015 elevated fellow », sur IEEE Fellows Directory.
↑ ISCB Fellow program.
↑ « ACM Recognizes 2017 Fellows for Making Transformative Contributions and Advancing Technology in the Digital Age », Association for Computing Machinery, 11 décembre 2017.
↑ (en) Dan Gusfield, Algorithms on Strings, Trees, and Sequences : Computer Science and Computational Biology, Cambridge/New York/Melbourne, Cambridge University Press, 1999, 534 p. (ISBN 0-521-58519-8, lire en ligne).
↑ Dan Gusfield et Robert W. Irving, The stable marriage problem : structure and algorithms, MIT Press, 1989, xvii+240 (ISBN 0-262-07118-5, présentation en ligne).
↑ Dan Gusfield, ReCombinatorics : The Algorithmics of Ancestral Recombination Graphs and Explicit Phylogenetic Networks, MIT Press, 2014, 600 p. (ISBN 978-0-262-02752-6, lire en ligne).

Liens externes

Dan Gusfield sur la page de l'université de Californie à Davis.
Dan Gusfield sur la page de MIT Press.
Publications de Dan Gusfield sur DBLP
Notices d'autorité :
- VIAF
- ISNI
- IdRef
- LCCN
- GND
- Belgique
- Pays-Bas
- Israël
- Tchéquie
- WorldCat

[1] (en) « Daniel Mier Gusfield », sur le site du Mathematics Genealogy Project.

[cv-2] Page personnelle de Gusfield.

[scv-3] Dan Gusfield - un brève autobiographie.

[4] Algorithms on Strings, Trees, and Sequences.

[5] Gusfield 2014.

[6] Dan Gusfield, « Very Simple Methods for All Pairs Network Flow Analysis », SIAM J. Comput, vol. 19, n^o 1,‎ 1990, p. 143-155.

[7] Robert W. Irving, Paul Leather et Dan Gusfield, « An efficient algorithm for the "optimal" stable marriage », Journal of the ACM, vol. 34, n^o 3,‎ 1987, p. 532-543.

[8] Gusfield et Irving 1989.

[Gusfield1991-9] Dan Gusfield, « Efficient algorithms for inferring evolutionary trees », Networks, vol. 21, n^o 1,‎ 1991, p. 19–28 (ISSN 0028-3045, DOI 10.1002/net.3230210104)

[10] Transactions on Computational Biology and Bioinformatics : Introduction.

[11] Dan Gusfield et Jens Stoye, « Linear time algorithms for finding and representing all the tandem repeats in a string », J. Comput. Syst. Sci., vol. 69, n^o 4,‎ 2004, p. 525-546.

[12] Dan Gusfield, Satish Eddhu et Charles H. Langley, « Optimal, Efficient Reconstruction of Phylogenetic Networks with Constrained Recombination », J. Bioinformatics and Computational Biology, vol. 2, n^o 1,‎ 2004, p. 173-214.

[13] Dan Gusfield, « Haploytyping as Perfect Phylogeny: Conceptual framework and efficient solutions », Proceedings of RECOMB,‎ 2002, p. 166-175.

[14] Dan Gusfield, « Haplotype inference by pure parsimony », dans Combinatorial Pattern Matching, Springer Verlag, 2003, p. 144-155.

[15] Dan Gusfield, « Inference of Haplotypes from Samples of Diploid Populations: Complexity and Algorithms », Journal of Computational Biology, vol. 8, n^o 3,‎ 2001, p. 305-323.

[16] Dan Gusfield, « The Multi-State Perfect Phylogeny Problem with Missing and Removable Data: Solutions via Integer-Programming and Chordal Graph Theory », Journal of Computational Biology, vol. 17, n^o 3,‎ 2010, p. 383-399.

[17] Yelena Frid et Dan Gusfield, « A simple, practical and complete $O(n^{3}\log n)$ -time Algorithm for RNA folding using the Four-Russians Speedup », Algorithms for Molecular Biology, vol. 5,‎ 2010, article n^o 13 (DOI 10.1186/1748-7188-5-13).

[18] « 2015 elevated fellow », sur IEEE Fellows Directory.

[19] ISCB Fellow program.

[20] « ACM Recognizes 2017 Fellows for Making Transformative Contributions and Advancing Technology in the Digital Age », Association for Computing Machinery, 11 décembre 2017.

[21] (en) Dan Gusfield, Algorithms on Strings, Trees, and Sequences : Computer Science and Computational Biology, Cambridge/New York/Melbourne, Cambridge University Press, 1999, 534 p. (ISBN 0-521-58519-8, lire en ligne).

[22] Dan Gusfield et Robert W. Irving, The stable marriage problem : structure and algorithms, MIT Press, 1989, xvii+240 (ISBN 0-262-07118-5, présentation en ligne).

[23] Dan Gusfield, ReCombinatorics : The Algorithmics of Ancestral Recombination Graphs and Explicit Phylogenetic Networks, MIT Press, 2014, 600 p. (ISBN 978-0-262-02752-6, lire en ligne).

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

[12]

[13]

[14]

[15]

[16]

[17]

[18]

[19]

[20]

[21]

[22]

[23]