Lorsque l'on désire construire un arbre phylogénétique, la première étape consiste à mettre en correspondance les sites des séquences comparables qui sont obtenus après l'étape d'alignement des séquences. Puis, une fois que les séquences sont alignées, différentes méthodes de génération d'arbres phylogénétiques, appelées méthodes d'inférence phylogénétique, peuvent être appliquées pour obtenir l'arbre qui reflète le mieux les données. Deux grandes catégories regroupent ces différentes méthodes:

1.  Méthodes basées sur les distances

2.  Méthodes basées sur les caractères

Les méthodes basées sur les distances utilisent une matrice d'estimation de la distance évolutive appelée matrice de dissimilarités, obtenue en comparant les paires de séquences. Elles comprennent, par exemple :

1.  La méthode UPGMA (Unweighted Pair Group Method with Arithmetic Mean) de Sokal et Michener (Sokal et Michener, r6), qui, par itérations successives, réduit progressivement la taille de la matrice fournissant l'ensemble des distances entre toutes les paires de séquences, et produit un arbre enraciné.

2.  La méthode du Neighbour Joining (Neighbor Joining NJ) de Naruya Saitou and Masatoshi Nei (Naruya et Masatoshi, r5), qui, à la différence avec la méthode UPGMA, effectue la recherche séquentielle des voisins en minimisant la longueur totale de l'arbre, et produit des arbres non enracinés.

Les défauts de la méthode UPGMA sont tels qu'elle n'a plus qu'un intérêt historique dans le cadre de l'inférence d'un arbre phylogénétique, puisqu'elle a été remplacée depuis lors par des méthodes plus avancées comme le Neighbour Joining ou la parcimonie dans un premier temps, puis par les techniques de maximum de vraisemblance ou algorithmes bayésiens utilisés aujourd'hui.

Figure 3: Expansion des noeuds par Neighbor Joining (Eric Fournier et Alexandre Iannello, 2009)

Les méthodes basées sur les caractères reposent sur un ou plusieurs caractères à étudier. Parmi ces méthodes probabilistes, les plus courantes sont basées sur:

1.  La méthode du maximum de vraisemblance (Maximum Likelihood ML) de Jerzy Neyman (Jerzy Neyman, r7), qui évalue, en terme de probabilités (vraisemblance), l'ordre des branchements et la longueur des branches d'un arbre dans le cadre dun modèle d'évolution probabiliste donné.

2.  La méthode du maximum de parcimonie  (Maximum Parcimony) de Warren Herbert Wagner (Joe Felsenstein, r8), qui consiste à rechercher parmi tous les arbres possibles et toutes les séquences possibles de noeuds ancestraux, la combinaison qui requiert le plus petit nombre de changements évolutifs dans l'arbre phylogénétique.

3.  La méthode bayésienne de Delsuc et Douzery (Delsuc et Douzery, r10), qui utilise une distribution à priori de tous les paramètres (topologies, longueurs des branches, taux relatifs des substitutions)

La méthode du maximum de vraisemblance est souvent décrite comme étant la meilleure méthode, cest-à-dire la plus efficace pour trouver l'arbre le plus proche de la réalité, mais son désavantage se situe au niveau des temps de calculs qui sont extrêmement longs. Le temps de calculs s'améliore dans la méthode du maximum de parcimonie mais la précision se perd comparée à la méthode du maximum de vraisemblance (Yoann Mouscaz, r9)

L'approche bayésienne comporte certains problèmes comme la nécessité d'avoir à définir une distribution à priori sur les hypothèses. Comme le calcul de la probabilité de toutes les topologies d'arbres est presque impossible, l'approche bayésienne est d'habitude couplée avec la technique appelée « Metropolis-coupled Markov chain Monte Carlo », qui permet de générer un échantillon de la distribution postérieure des topologies d'arbres (Huelsenbeck et Ronquist, r11)

Figure 4: Une chaîne de Markov pour une séquence d'ADN (Abdoulaye Baniré Diallo, r16)

L'idée de la chaîne de Markov, prenant la forme d'une marche guidée à travers l'espace multidimensionnel des paramètres est par analogie avec la trajectoire dun randonneur aveugle obéissant à des règles simples de déplacement sur un paysage. Ainsi, si le randonneur est autorisé à se déplacer pendant une durée suffisamment longue, la totalité de la surface va être visitée. La technique de la chaîne de Markov peut être utilisée pour estimer une distribution de probabilité en échantillonnant les valeurs de ces paramètres de façon périodique. L'approximation de la distribution sera d'autant plus exacte que le nombre de pas effectués par la chaîne de Markov sera élevé (Holder et Lewis, r16)