FM-index

En informatique, un FM-index est une structure d'indexation compressée sans perte, fondée sur la Transformée de Burrows-Wheeler, qui a des similitudes avec le tableau des suffixes. Cette structure de données a été créée par Paolo Ferragina et Giovanni Manzini[1], qui la décrivent comme étant un index multi-usages basé sur une structure de donnée astucieuse. Le nom signifie « Full-text index in Minute space »[2],[3].

Cet index peut, en plus de la compression, être utilisé pour trouver de façon efficace le nombre d’occurrences d’un motif dans le texte compressé, ainsi que pour localiser la position de chaque occurrence du mot recherché dans le texte compressé. Aussi bien le temps que l'espace de stockage requis ont une complexité sublinéaire par rapport à la taille des données d’entrée. C'est-à-dire que le temps d'exécution et l'espace de stockage requis ne sont pas proportionnels à la taille des données d'entrée.

Le FM-index a été utilisé entre autres en bio-informatique[4].

Cadre

Utiliser un index est une stratégie commune pour rechercher efficacement dans un vaste corpus de texte. Lorsque le texte est plus grand que ce que peut contenir la mémoire principale de l’ordinateur, il est nécessaire de compresser non seulement le texte, mais aussi l’index. Lorsque le FM-index a été introduit, plusieurs solutions avaient déjà été suggérées pour atteindre ce double but. Elles reposaient sur des méthodes de compression traditionnelles qui essayaient aussi de résoudre le problème de compression d'index. En revanche, FM-index utilise un index compressé de façon native, ce qui signifie qu’il est simultanément capable de compresser les données et d'indexer.

Structures FM-index

Un FM-index est créé en prenant d'abord la transformée de Burrows-Wheeler (BWT) du texte d’entrée. Par exemple, la BWT de la chaîne T = « abracadabra » est « ard$ rcaaaabb », et ici elle est représentée par la matrice M où chaque ligne est une rotation du texte, et les lignes ont été triées lexicographiquement. La transformation correspond à la dernière colonne intitulée L.

I	F		L
1	$	abracadabr	a
2	a	$abracadab	r
3	a	bra$abraca	d
4	a	bracadabra	$
5	a	cadabra$ab	r
6	a	dabra$abra	c
7	b	ra$abracad	a
8	b	racadabra$	a
9	c	adabra$abr	a
10	d	abra$abrac	a
11	r	a$abracada	b
12	r	acadabra$a	b

La BWT en soi permet une compression avec, par exemple, move-to-front et le codage de Huffman, mais la BWT à d'autres utilisations. Les lignes de la matrice sont essentiellement les suffixes triés du texte, ce qui correspond au tableau des suffixes. Ce lien entre le tableau des suffixes et la BWT est au cœur du FM-index.

Il est possible de faire un tableau de correspondance entre la dernière et la première colonne LF(i) depuis un index i vers un index j, tel que F [j] = L [i], avec l’aide d’une table C [c] et "OCC (c, k). C [c] est une table qui, pour chaque caractère c dans l’alphabet, contient le nombre d’occurrences de caractère lexicalement plus petits qui sont contenus dans le texte. La fonction OCC (c, k) est le nombre d’occurrences du caractère c dans le préfixe "L [1..k]. Ferragina et Manzini a montré [1] qu’il est possible de calculer des OCC (c, k) en temps constant.

C[c] de "ard$rcaaaabb" c $ a b c d r C[c] 0 1 6 8 9 10

Le tableau de correspondance entre la dernière et la première colonne peut maintenant être défini comme LF(i) = C [L [i]] + Occ (L [i], i). Par exemple, en rang 9, L est 'a' et le même 'a' se trouvent sur la ligne 5 dans la première colonne F, donc LF(9) devrait être 5 et LF(9) = C [a] + Occ (a, 9) = 5. Pour toute ligne i de la matrice, le caractère dans la dernière colonne L [i] précède le caractère dans la première colonne F [i] aussi en T. Enfin, si L [i] = T [k], puis L[LF(i)] = T [k - 1], et en utilisant l’égalité, il est possible d’extraire une chaîne de T de L. Le FM-index lui-même est une compression de la chaîne L avec C et OCC, mais aussi des informations qui mappe une sélection d’indices en L à des positions dans la chaîne d’origine T.

Occ(c, k) de "ard$rcaaaabb" a r d $ r c a a a a b b 1 2 3 4 5 6 7 8 9 10 11 12 $ 0 0 0 1 1 1 1 1 1 1 1 1 a 1 1 1 1 1 1 2 3 4 5 5 5 b 0 0 0 0 0 0 0 0 0 0 1 2 c 0 0 0 0 0 1 1 1 1 1 1 1 d 0 0 1 1 1 1 1 1 1 1 1 1 r 0 1 1 1 2 2 2 2 2 2 2 2

Compter

L’opération count prend un motif P [1..p] et retourne le nombre d’occurrences de ce motif dans le texte original T. Comme les lignes de la matrice M sont triées, et qu'elles contiennent chaque suffixe de T, les occurrences du motif P seront côte à côte dans une unique plage continue. Cette opération est réitérée de façon rétrograde sur le motif. Pour chaque caractère dans le motif, l'ensemble de lignes qui possède ce caractère comme suffixe, est trouvé. Par exemple, la recherche du motif « bra » dans « abracadabra » suit les étapes suivantes :

1. Le premier caractère que nous recherchons est ' a', le dernier caractère dans le motif. L'ensemble de lignes initial est définie sur [ C [a] + 1..C [a + 1] = [2..6]. Cet ensemble de lignes sur L représente chaque caractère de T, qui possède un suffixe commençant par a.
2. Le prochain caractère à rechercher est r. Le nouvel ensemble de lignes est [ C [r] + Occ (r, start-1) + Occ (r, fin), 1..C [r]] = [ 10 + 0 + 1..10 + 2] = [ 11..12], si début est l’index de début de la plage et fin est la fin. Cet ensemble de lignes sur L contient tous les caractères de T qui ont des suffixes commençant par ra.
3. Le dernier caractère à regarder est b. Le nouvel ensemble de lignes est [ C [b] + Occ (b, start-1) + 1..C [b] + Occ (b, fin)] = [ 6 + 0 + 1..6 + 2] = [ 7..8]. cet ensemble de lignes sur L consiste en tous les caractères qui ont un suffixe commençant par bra. Maintenant que l'ensemble du motif est traitée, le compte est identique à la taille de la plage : 8-7 + 1 = 2.

Si la plage est vide ou si les limites de l'ensemble de lignes se croisent mutuellement avant que l’ensemble du motif soit investigué, cela signifie que P n'est pas présent dans T. Comme OCC (c, k) peut être effectué en temps constant, le comptage peut s'accomplir en temps linéaire proportionnel à la longueur du motif : Temps de O(p).

Localiser

L’opération localiser prend comme entrée un index d’un caractère dans L et retourne sa position i en T. Par exemple locate(7) = 8. Pour trouver toutes les occurrences d’un motif, il faut tout d’abord trouver la plage de suffixes de T dont le motif est préfixe, de la même manière que celle pour l’opération compter. Ensuite, il reste à trouver la position de chaque suffixe de cette plage dans T.

Pour faire correspondre un index dans L en un index dans T, un sous-ensemble des indices en L est associé à une position en T. Si L [j] a une position qui lui est associée, trouver locate(j) est trivial. S'il n’y a pas de positions associée, la recherche se poursuit sur la chaîne avec LF(i) jusqu'à ce qu’un index associé soit trouvé. En associant un nombre adéquat d’indices, on trouvera une limite supérieure. L’opération trouver peut être implémentée pour trouver les occurrences d'occ P [1..p] dans un texte T [1..u] en O (p + occ log ^ε u) temps avec ${\displaystyle O(H_{k}(T)+{{\log \log u} \over {\log ^{\epsilon }u}})}$ bits par symbole d’entrée pour toute k ≥ 0[1].

Améliorations

Les auteurs ont mis au point des améliorations à leur approche première et ont nommé cette nouvelle méthode de compression « FM-Index version 2 »[5]. Une autre amélioration, le FM "respectueux de l’alphabet", combine l’utilisation de la stimulation de compression et les ondelettes [6] pour réduire considérablement l’utilisation de l’espace dans le cas d'utilisation d'alphabets de grande taille.

Applications

Localisation de séquences d'ADN sur un génome

Le FM-index a été appliqué avec succès (> 2000 citations) à l’alignement de séquence génomique, voir http://bowtie-bio.sourceforge.net/index.shtml.

Notes et références

1. Paolo Ferragina and Giovanni Manzini (2000). "Opportunistic Data Structures with Applications". Proceedings of the 41st Annual Symposium on Foundations of Computer Science. p. 390.
2. Le nom signifie peut-être aussi index de Ferragina et Manzini ?
3. Paolo Ferragina et Giovanni Manzini (2005). "« Indexing Compressed Text »", Journal of the ACM, 52, 4, (Jul. 2005). p. 553-.
4. Simpson, Jared T. and Durbin, Richard (2010). "Efficient construction of an assembly string graph using the FM-index". Bioinformatics, 26, 12 (Jun. 17). p. i367.
5. Paolo Ferragina et Rossano Venturini « FM-Index version 2 »
6. P. Ferragina, G. Manzini, V. Mäkinen and G. Navarro. An Alphabet-Friendly FM-index. In Proc. SPIRE'04, pages 150-160. LNCS 3246.