2-04. Recherche textuelle

Imaginons le brin d’ADN avec la séquence de nucléotides suivante :

Quel algorithme concevoir pour permettre de savoir si ce brin d'ADN contient une séquence donnée (par exemple ATATG), et si oui, en quelle position ?

Nous allons commencer par le premier algorithme qui nous vient à l'esprit (on parle souvent d'algorithme « naïf ») :

• On examine chaque lettre du brin d’ADN. Si elle correspond à la première lettre du motif recherché (ici ATATG), alors, on compare la lettre suivante du brin avec la lettre suivante du motif, etc.
• Si, à un moment les deux lettres comparées sont différentes, on décale l’analyse à la lettre suivante sur le brin.
• On poursuit jusqu’à ce que le motif soit trouvé ou jusqu’à l’examen complet du brin.

Cet algorithme naïf peut, selon les situations demander un très grand nombre de comparaisons, ce qui peut entraîner un très long temps de calcul avec des chaines très très longues. L'algorithme de Boyer-Moore, que l’on va voir au paragraphe suivant, permet de faire mieux en termes de comparaisons à effectuer

• Étudier l’algorithme de Boyer-Moore pour la recherche d’un motif dans un texte.

L'algorithme de Boyer-Moore est un algorithme de recherche de motif particulièrement efficace, inventé en 1977. Celui qui est présenté ici, au programme de terminale, est en réalité une version simplifiée appelée algorithme de Boyer-Moore-Horspool

On commence par aligner le texte et le motif par le début, comme dans le cas de l’algorithme naïf. Mais on compare la dernière lettre du motif (G) avec celle du même rang dans le texte (C).
Ici, il n’y a pas de correspondance.

On cherche alors la première occurence de la lettre C (c’est-à-dire la lettre du texte qui a été comparée à la dernière lettre du motif) dans le motif, en parcourant le motif vers son début.
Ici, le motif ne contient pas cette lettre. On peut donc s’économiser toutes les comparaisons qui aligneraient une des lettres du motif avec ce C.

On peut donc décaler le motif d’un nombre de rang égal à sa longueur (ici 5).

Après décalage de 5 rangs, on constate que le G du motif ne correspond pas au A du texte. Cependant, A est présent dans le motif. Le premier A du motif se trouve après un décalage de 2 rangs. On décale donc le motif de 2 rangs pour effectuer une nouvelle comparaison.

On a maintenant une correspondance sur le G. Cependant, la lettre précédente du motif (T), ne correspond pas à la lettre du texte (A).

G n’étant pas présent ailleurs dans le motif, on décale le motif de 5 rangs vers la droite.

On continue comme ceci jusqu’à trouver le motif ou arriver à la fin du texte. Comme vous l’avez compris, cette méthode permet de réaliser moins de comparaisons que la méthode « naïve ». Elle est donc plus rapide. Elle est d’ailleurs d’autant plus efficace que le motif est long.

Animation de l’algorithme de Boyer-Moore

			def creer_table_decalage(chaine):
				decalage = {}
				for i in range(...):
					...
				return decalage
		

			def test_creer_table_decalage():
				ctr = creer_table_decalage
				assert ctr("bonjour") == {"b": 6, "o": 2, "n": 4, "j": 3, "u": 1}
				assert ctr("dab") == {"d": 2, "a": 1}
				assert ctr("dabab") == {"d": 4, "a": 1, "b": 2}
				assert ctr("ACTGACTGACTG") == {"A": 3, "C": 2, "T": 1, "G": 4}
				print ("Tests de création de table de décalage réussis")
		

			def boyer_moore(texte, motif):
				table = table_décalage(motif)
				i = 0
				while len(texte) - i >= len(motif):
					j = len(motif)-1
					while texte[i+j] == motif[j]:
						if j == 0:
							return i
						j = j - 1
					if texte[i+len(motif)-1] in table:
						deplacement = table[texte[i+len(motif)-1]]
					else:
						deplacement = len(motif)
					i = i + deplacement
				return -1
		

				def creer_table_decalage(chaine):
					decalage = {}
					for i in range(len(chaine)-1):
						decalage[chaine[i]] = len(chaine) - i - 1
					return decalage