Dans cette thèse, nous nous intéressons à la reconstruction d'arbres évolutifs (ou ``phylogénies'') retraçant l'histoire évolutive d'espèces vivantes. Afin d'obtenir une estimation aussi proche que possible de la structure d'une phylogénie inconnue, nous prenons le parti pris de produire une phylogénie ne contenant que des arêtes fiables, quitte à ne retrouver qu'une partie de la phylogénie recherchée. Dans le cadre de cette problématique, nous explorons deux catégories de méthodes :
Les méthodes à résolution décroissante que
nous proposons reposent sur des techniques de rééchantillonnage,
et plus particulièrement sur celle du bootstrap. Dans un premier
temps, nous montrons comment détourner la procédure de bootstrap,
telle qu'elle fut introduite en reconstruction phylogénétique,
pour proposer une estimation fiable d'une phylogénie d'espèces.
Puis, nous définissons une deuxième procédure bootstrap,
dont l'originalité est d'estimer, en fonction de la qualité
du jeu de données et de la méthode de reconstruction utilisée,
le nombre d'arêtes que doit comporter la phylogénie proposée
pour avoir une erreur minimum. Cette nouvelle procédure donne des
résultats d'aussi bonne qualité que la précédente,
en des temps plus courts.
Les méthodes à résolution croissante que nous proposons
reposent sur un principe d'optimisation combinatoire lié aux quadruplets
d'espèces : on infère d'abord des phylogénies sur
quatre espèces, qu'on cherche ensuite à combiner en une phylogénie
sur l'ensemble des espèces, de façon à optimiser un
certain critère.
Dans ce cadre, nous montrons que le problème du sous-ensemble maximum
de quadruplets, équivalent à un arbre, peut être résolu
de façon exacte en temps polynômial, O(n^4). En associant
l'algorithme obtenu avec un principe simple d'inférence de phylogénies
sur 4 espèces, nous obtenons la méthode Q*, ne proposant
que des arêtes combinatoirement sûres. Nous caractérisons
la boule de consistance de cette méthode, au sens de la norme Loo.
En utilisant des arguments probabilistes nous donnons une borne sur la
vitesse de convergence de cette méthode (pour les modèles
de l'évolution classiques), montrant que cette vitesse est au pire
polynomiale sous certaines conditions. Les résultats expérimentaux
montrent que la méthode Q* infère en pratique très
peu d'arêtes incorrectes et retrouve généralement une
proportion non-négligeable des arêtes correctes.
Enfin, pour compléter l'arbre inféré par la méthode
Q*, parfois trop conservatrice, nous proposons un algorithme agglomératif
en basé sur les quadruplets et de complexité O(n^4).
Les simulations montrent que cet algorithme rapproche significativement
l'arbre proposé par la méthode Q* de la phylogénie
correcte.
Diverses simulations montrent que les méthodes, à résolution croissante et à résolution décroissante, que nous proposons obtiennent de meilleurs résultats que les méthodes traditionnellement utilisées (p.ex. le Neighbor Joining et le Maximum de Parcimonie) pour estimer la structure d'une phylogénie inconnue.