Associated Team HELIX-USP

Participants

The coordinator of the Brazilian side is Prof. Yoshiko Wakabayashi, associated professor at the Department of Computer Science of the University of São Paulo. Prof. Wakabayashi obtained her Dr. rer. nat. degree at the University of Augsburg, Germany, in 1986, and her Habilitation at the University of São Paulo in 1995. Her research interest includes combinatorial optimization and graph theory. More recently she has focused her research in approximation algorithms (having major contributions in packing problems) and computational biology. Prof. Wakabayashi has headed joint projects with French institutions and also with German institutions, and currently is the coordinator of a CNPq-project involving 4 countries of South America (Argentina, Brazil, Chile and Uruguay), with approximately 50 participants from 8 important universities in South America. She is also currently a member of the computer science area committe at CAPES, one of the main federal funding research agencies in Brazil. She has advised several PhD and MSc students, has a book on polyhedral combinatorics with one of the members of this project and participated in the writing of a book on approximation algorithms. More information on her CV is available from her web page: http://www.ime.usp.br/~yw/.

The HELIX and USP teams are complementary in the following sense. The French part of the team is strongly active in the area of computational biology. Most of its members come from computer science or mathematics, but some have majors in biology or bioinformatics. The team is also actively in contact with biologists and maintains a strong collaboration with researchers in molecular biology. Its coordinator, Dr. Marie-France Sagot, has a background in computer science, more specifically algorithmics. She worked for four years at the Pasteur Institute in Paris and is now a Director of Research at the INRIA. She is physically located at the Claude Bernard University in Lyon, and belongs to the Laboratoire of Biometry and Evolutionary Biology of the University. The Brazilian part of the team is strongly active in combinatorial optimization, computational complexity and development of algorithms in general, and has, in the past years, invested in the area of computational biology. Almost all of them are members of the Combinatorics and Combinatorial Optimization Research Group, at the Department of Computer Science of the University of São Paulo, Brazil.

This collaboration will be very beneficial for both sides. The Brazilian members will thus benefit from the expertise in computational biology from the French members while the latter will be able to count on the general experience in combinatorial optimization, computational complexity and algorithmics of the Brazilian members to reinforce these aspects inside the French team. The team counts with a number of PhD students on both sides that will also benefit from this collaboration.

It is important to note that the collaboration has already existed for many years now. Dr. Marie-France Sagot was a student at the University of São Paulo before coming to France for the DÉA. She kept her contacts at the USP. Such contacts lead to an official collaboration through a CAPES-COFECUB project from 1999 to 2001. The coordinators from both sides in particular, Prof. Yoshiko Wakabayashi and Dr. Marie-France Sagot, have been collaborating for many years. Recently, Springer-Verlag published a book named Recent Advances in Algorithms and Combinatorics, edited by B. Reed and C.L. Sales (CMS Books in Mathematics, 2003), with several chapters. One of them, Pattern inference under many guises [3], was written by the two coordinators of this project, and addresses part of the topics that will be under investigation within this project. One of the members of the Brazilian team, when a PhD student, spent 9 months in a research mission under the supervision of the French coordinator (two papers, one accepted and one submitted, resulted from the mission [1] [2]), and recently another Brazilian student, who is now finishing his PhD, did the same. Currently a member of the Brazilian team is in a research visit with the French partners for a period of 6 weeks. This visit is being funded (informally) by the INRIA (stay) and the ProNEx 107/97 - MCT/CNPq project (Proc. CNPq 664107/1997-4, plane tickets).

There is a long history of past collaboration between research centers in France and the Department of Computer Science of the University of São Paulo (DCC-IME-USP). Most of the collaborations were funded by COFECUB jointly with one of the Brazilian research agencies. Such collaborations started years ago in the area of automa theory, involving Prof. Dominique Perrin (France), Prof. Jean-Eric Pin (France), Prof. Imre Simon (Brazil) and others. More recently, there were collaborations also between the group of image processing from the DCC-IME-USP, through Prof. Junior Barrera, and the Centre de Morphologie Mathématique (Paris), through Prof. Jean Serra. Currently, there is a CAPES-COFECUB project with the vision group in the DCC-IME-USP (Prof. Roberto Marcondes) and the ENST in Paris (Prof. Isabelle Demeure), and an USP-COFECUB with a group in Grenoble (the coordinator on the Brazilian side is Prof. Alfredo Goldman), where there is also an informal collaboration that involves the INRIA. Prof. Siang Song, head of the parallel computing research group of the DCC-IME-USP, had two visits funded by a Brazilian agency BID/USP to the École Normale Supérieure of Lyon. Finally, the group involved in the current proposal had a CAPES-COFECUB project recently (1999-2001).

[1] E.M. Rodrigues, M.-F. Sagot, and Y. Wakabayashi, Some approximation results for the maximum agreement forest problem, Proceedings of APPROX-RANDOM 2001 (Approximation, Randomization, and Combinatorial Optimization: Algorithms and Techniques) (M. Goemans and K. Jansen and J.D.P. Rolim abd L. Trevisan, eds.), Lecture Notes in Computer Siences, vol. 2129, Springer-Verlag, 2001, pp. 159--169.
[2] E.M. Rodrigues, M.-F. Sagot, and Y. Wakabayashi, The Maximum Agreement Forest Problem: approximation algorithms and computational experiments, submitted.
[3] M.-F. Sagot and Y. Wakabayashi, Pattern inference under many guises. Recent advances in algorithms and combinatorics, 245--287, CMS Books Math./Ouvrages Math. SMC, 11, Springer, New York, 2003.