Le cauchemar des systèmes de coordonnées en bioinformatique

En bio­in­for­ma­tique, quand on mani­pule des génomes, des anno­ta­tions, des fichiers d’alignement, des variants ou des inter­valles (exons, régions régu­la­trices, etc.), on est rapi­de­ment confron­té à deux notions fon­da­men­tales qui condi­tionnent la manière dont les posi­tions sont décrites et inter­pré­tées :

1. le sys­tème d'indexation : com­mence-t-on à comp­ter à 0 ou à 1 ? Cer­tains for­mats adoptent une numé­ro­ta­tion com­men­çant à 0, comme dans de nom­breux lan­gages de pro­gram­ma­tion. D’autres optent pour une numé­ro­ta­tion com­men­çant à 1, plus intui­tive car conforme à notre manière natu­relle de comp­ter.
2. le type d’intervalle : les bornes sont-elles inclu­sives ou non ?
   Chaque inter­valle pos­sède un début et une fin, mais ces bornes peuvent être incluses ou exclues. On peut ain­si repré­sen­ter les régions à l’aide d’intervalles « inclu­sif-inclu­sif », « inclu­sif-exclu­sif », « exclu­sif-inclu­sif » ou « exclu­sif-exclu­sif ».

Ces deux dimen­sions défi­nissent ensemble le sys­tème de coor­don­nées uti­li­sé. Les maî­tri­ser per­met d’interpréter cor­rec­te­ment les posi­tions géno­miques et de tra­vailler serei­ne­ment avec des don­nées hété­ro­gènes. Dans cet article, nous allons pré­sen­ter clai­re­ment ces sys­tèmes de coor­don­nées et, je l’espère, vous aider à déjouer les pièges les plus cou­rants.

Creu­sons main­te­nant ces deux concepts plus en détail.

Le système d'indexation

Avant d’aborder les sys­tèmes de coor­don­nées uti­li­sés en géno­mique, il est utile de faire un détour par l’informatique. En pro­gram­ma­tion, l’indexation désigne la manière dont on numé­rote les élé­ments d’une struc­ture ordon­née, comme un tableau ou une chaîne de carac­tères. Deux conven­tions prin­ci­pales existent : l’indexation 0-based et la 1-based.

Indexation 0-based

Dans une indexa­tion 0-based, le pre­mier élé­ment est numé­ro­té 0, le second 1, et ain­si de suite.

Cette conven­tion est his­to­ri­que­ment liée aux lan­gages de bas niveau, notam­ment C, où l’accès à un élé­ment d’un tableau se fait par cal­cul d’un déca­lage (off­set) par rap­port à l’adresse mémoire de base. La pre­mière entrée est à zéro de l'origine du tableau, la deuxième entrée est à un déca­lage de 1. Ce lien direct entre index et déca­lage rend l’indexation 0-based très natu­relle pour les machines et a influen­cé de nom­breux lan­gages modernes, comme Python, Java, C++, etc.

Indexation 1-based

À l’inverse, l’indexation 1-based numé­rote le pre­mier élé­ment 1, le deuxième 2, etc.
Elle est plus intui­tive pour l’humain puisqu’elle s’aligne avec notre manière natu­relle de comp­ter : le pre­mier élé­ment est “1ᵉʳ”, pas “0ᵉ”.
Cette conven­tion est uti­li­sée dans des lan­gages comme R, For­tran, MATLAB, ou encore dans cer­taines inter­faces orien­tées uti­li­sa­teurs.

Ces deux tra­di­tions d'indexation, le 0-based issu de l'informatique et le 1-based héri­té des usages humains et mathé­ma­tiques, se retrouvent aujourd’hui dans les for­mats géno­miques.
Ain­si, cer­tains fichiers uti­lisent le 0-based comme le for­mat BED ou BAM, tan­dis que d’autres reposent sur le 1-based comme le GFF/​GTF ou SAM. Les lan­gages de pro­gram­ma­tion reflètent la même diver­si­té. D’où l’importance d'identifier clai­re­ment le sys­tème d'indexation employé par les for­mats que l’on mani­pule ain­si que par les outils ou lan­gages avec les­quels on tra­vaille.

Notion d’intervalles ouverts /​ fermés

Au-delà du choix de l’indexation (0-based ou 1-based), la façon dont on inclut ou exclut les bornes d’un inter­valle joue un rôle cru­cial dans la repré­sen­ta­tion des régions géno­miques.
Cette notion, issue des mathé­ma­tiques, per­met de pré­ci­ser si les posi­tions de début et de fin appar­tiennent ou non à la région décrite. On dis­tingue les bornes fer­més qui sont inclus dans l'intervalle noté par des cro­chets "[]" et les bornes ouvertes noté par des paren­thèses "()". Ce qui nous donne un total de 4 pos­si­bi­li­tés : fer­mé-fer­mé, fer­mé-ouvert, ouvert-fer­mé, ouvert-ouvert.

Regar­dons main­te­nant ensemble, plus en détails, ces quatre types d'intervalles.

Intervalles avec début exclusif (a, b] et (a,b)

En mathé­ma­tique ou sta­tis­tique où l'on ren­contre sou­vent des valeurs conti­nues il est pos­sible de ren­con­trer ces usages. Mais les posi­tions géno­mique cor­res­pondent à des enti­tés dis­crètes… une base existe à une posi­tion entière ! Exclure une base « en amont » n'est pas vrai­ment pra­tique. Exclure aus­si la fin devient vrai­ment bizarre, l'intervalle perd ses repères natu­rels et nous aus­si par l'occasion. Quid de l'exclusion uni­que­ment de la base « en aval » [a, b) ? On va voir plus loin que cette der­nière à fina­le­ment de bonnes rai­sons d'exister.

Intervalle fermé [a, b]

Il cor­res­pond à la manière “natu­relle” de comp­ter chez l’humain :
si l’on dit qu’une région com­mence à la posi­tion 5 et se ter­mine à 7, on inclut les posi­tions 5, 6 et 7 donc 3 bases. C’est pour­quoi ce modèle est uti­li­sé dans des for­mats géno­miques orien­tés anno­ta­tion humaine, comme GFF/​GTF, SAM ou VCF.

Mais ce choix intui­tif devient moins pra­tique dès qu’on sou­haite cal­cu­ler une lon­gueur ou mani­pu­ler des régions en pro­gram­ma­tion.

Pour la lon­gueur, il faut pen­ser à ajou­ter +1 :

Pour la mani­pu­la­tion pro­gram­ma­tique, l’intervalle fer­mé-fer­mé ne s’aligne pas avec le "sli­cing", la conven­tion la plus répan­due en infor­ma­tique pour accé­der à une por­tion d’un tableau ou d’une chaîne de carac­tères.
Dans la majo­ri­té des lan­gages, que l’on dis­pose d’un sli­cing natif (Python) ou de fonc­tions dédiées (Java, JavaS­cript, C++), les sous-séquences sont défi­nies selon un modèle semi-ouvert : inclure l’index de début, exclure l’index de fin, c’est-à-dire un inter­valle de type [start, end). (Dans le cas de C++ on spé­ci­fie un début + une lon­gueur, ce qui abou­tit aus­si à un com­por­te­ment com­pa­tible avec un inter­valle semi-ouvert).

Il existe des excep­tions, comme R, qui adopte une logique inclu­sive (x[1:5] ren­voie les posi­tions 1 à 5). Mais la conven­tion domi­nante dans la plu­part des lan­gages reste l’intervalle semi-ouvert. Voir l'antisèche plus loin pour voir les "excep­tions".

Avec un inter­valle fer­mé-fer­mé [a, b], extraire la région cor­res­pon­dante dans ces lan­gages impose donc un ajus­te­ment de la borne de fin :

pour inclure b, il faut aller jusqu’à b+1 :

Autre­ment dit, une borne droite « fer­mée » dans les for­mats humains doit être conver­tie en borne « ouverte » dans les fonc­tions d’extraction, ce qui intro­duit une étape men­tale sup­plé­men­taire… et une source clas­sique d’erreurs.

Intervalle semi-ouvert [a, b)

Ici, la borne de début "a" est incluse, mais la borne de fin "b" est exclue. Ce modèle uti­li­sé dans des for­mats comme BED ou BAM peut sem­bler contre-intui­tif au pre­mier abord, mais il sim­pli­fie énor­mé­ment les opé­ra­tions.

La lon­gueur devient sim­ple­ment :

Le chaî­nage d’intervalles conti­gus se fait natu­rel­le­ment :

Le pre­mier s’arrête À 7 (exclue), le second com­mence À 7 (inclus), aucune base ne se che­vauche.

Et sur­tout, il est par­fai­te­ment ali­gné avec la logique des slices uti­li­sés en pro­gram­ma­tion. Extraire [a, b) revient sim­ple­ment à écrire (e.g. python):

sans aucune trans­for­ma­tion, ni +1, ni -1.

Les deux systèmes de coordonnées utilisés en bioinformatique

Si l’on com­bine les deux types d’indexation (0-based, 1-based) et les quatre types d’intervalles (fer­més, ouverts, les deux semi-ouvertes), on obtient 8 sys­tèmes de coor­don­nés pos­sibles. Sur ces 8 pos­si­bi­li­tés toutes ne sont pas uti­li­sés en bio­in­for­ma­tique, heu­reu­se­ment ! Seules deux formes d'intervalles sont réel­le­ment uti­li­sées. Mais quelle sont-elle ? Et Pour­quoi ? Je sais vous tré­pi­gnez d'impatience de savoir le fin mot de l'histoire, on y arrive dou­ce­ment.

On peut com­men­cer par écar­ter les inter­valles dont la borne de début est ouverte comme (a,b] et (a,b) car que ce soit en 0-based ou 1-based, les argu­ments avan­cé dans le para­graphe pré­cé­dent reste entier. Exclure le pre­mier élé­ment d'un inter­valle est pas un choix agréable pour la logique humaine. Ca n'aide pas à s'encrer dans l'espace du réel. Les posi­tions que nous cher­chons à mani­pu­ler sont des enti­tés dis­crètes, pas des valeurs conti­nues. ll n’y a donc aucun sens bio­lo­gique à exclure arbi­trai­re­ment la pre­mière "base" d’une région. S'il n'y a pas de rai­sons valables ou une logique à laquelle se rac­cro­cher pour impo­ser quelque chose de peu intui­tif pour­quoi s'embêter…

Le 1-based fer­mé-fer­mé [a, b] suit la logique intui­tive humaine : on compte à par­tir de 1 et on inclut natu­rel­le­ment les deux bornes. Uti­li­ser le 0-based fer­mé-fer­mé [a, b] est contre-intui­tif, il mélange la logique infor­ma­tique et la logique humaine. De plus, les gains dans la sim­pli­fi­ca­tion de cal­cul de lon­gueur et d'extraction sont per­dus. Pour la lon­gueur il fau­drait faire end - start + 1 au lieu de end - start. Et pour l'extraction de région il fau­drait faire s[a : b+1] au lieu de s[a : b].

Le sys­tème de d'indexation 0-based pro­vient d'une logique infor­ma­tique. Asso­cié au type d'intervalle semi-ouvert [a,b), il devient fort pra­tique. Il suit plei­ne­ment les concepts infor­ma­tique en s'alignant sur les prin­cipes de sli­cing ,et sim­pli­fie les cal­culs. En ce sens l'utilisation 1-based semi-ouvert [a, b) semble être une aber­ra­tion. Il mélange la logiques humaine du 1-based et la logique infor­ma­tique du semi-ouvert. En com­bi­nant les deux mondes, fina­le­ment on annule les avan­tages des deux. Il n'est ni intui­tif : [1,100) : la lon­gueur ferait 99 bases ; ni pra­tique du fait de son éloi­gne­ment du concept infor­ma­tique du sli­cing : pour l'extraction d'une région il fau­drait faire s[start -1 : end -1] à la place de s[start - 1 : end]. A la rigueur le seul point qui serait sim­pli­fié serait le cal­cul de la lon­gueur d'une région qui serait end - start. Mais il sem­ble­rait que ca n'ai pas était suf­fi­sant pour gar­der cette approche.

Au final seuls deux sys­tèmes de coor­don­nés sont uti­li­sés en pra­tique :
le 1-based fer­mé-fer­mé [a, b] et le 0-based semi-ouvert [a, b). Ce n’est pas un hasard : ce sont les deux seuls couples qui conservent une logique cohé­rente dans leur domaine d’origine.

Conclusion

La coexis­tence des dif­fé­rents sys­tèmes de coor­don­nées en géno­mique n’est pas le fruit du hasard : elle découle d’héritages his­to­riques et de logiques pra­tiques.
Du côté infor­ma­tique, les pre­miers lan­gages de bas niveau ont popu­la­ri­sé l’indexation 0-based, car elle cor­res­pond direc­te­ment au cal­cul d’un déca­lage en mémoire (off­set). Cette approche s’est ensuite natu­rel­le­ment com­bi­née avec le modèle d’intervalle half-open [start, end), très pra­tique pour rai­son­ner en termes de slices, cal­cu­ler des lon­gueurs (end − start) ou conca­té­ner des seg­ments sans ambi­guï­té. C’est pour­quoi de nom­breux for­mats bio­in­for­ma­tiques mani­pu­lés par des outils pro­gram­ma­tiques, comme BED, uti­lisent cette conven­tion.

En paral­lèle, une autre tra­di­tion s’est impo­sée : celle du 1-based ful­ly clo­sed [start, end]. Plus intui­tive pour l’esprit humain, elle cor­res­pond à la manière dont nous comp­tons natu­rel­le­ment les posi­tions (« la pre­mière base est la 1ᵉ »), et faci­lite la lec­ture directe d’annotations géno­miques. Ce modèle est domi­nant dans les for­mats plus orien­tés « bio­lo­gie », tels que GFF/​GTF ou VCF, sou­vent uti­li­sés comme inter­faces entre spé­cia­listes humains.

Ain­si, la bio­in­for­ma­tique se situe à la ren­contre de deux cultures :
• l’une, infor­ma­tique, opti­mi­sée pour les cal­culs et la mani­pu­la­tion algo­rith­mique,
• l’autre, bio­lo­gique, tour­née vers l’interprétation humaine.

Aucune conven­tion n’est intrin­sè­que­ment meilleure : cha­cune répond à une logique dif­fé­rente. L’essentiel est d’être conscient de ces choix, de les docu­men­ter clai­re­ment, et de mani­pu­ler les conver­sions avec soin pour évi­ter les erreurs de type « off-by-one ». En com­pre­nant l’origine de ces sys­tèmes et leurs impli­ca­tions, on peut mieux navi­guer entre for­mats et outils, et garan­tir la fia­bi­li­té des ana­lyses géno­miques.

Il faut gar­der en tête que lorsqu’on uti­lise un for­mat 1-based dans un lan­gage ou une biblio­thèque 0-based, il est néces­saire d’effectuer les conver­sions adé­quates. Cer­taines librai­ries appliquent ces trans­for­ma­tions auto­ma­ti­que­ment. Par exemple, le for­mat SAM, défi­ni en 1-based, est conver­ti en 0-based lorsqu’il est mani­pu­lé via pysam. Cette auto­ma­ti­sa­tion est pra­tique, mais peut aus­si deve­nir source d’erreur si l’on ignore qu’elle a lieu.

En résu­mé, maî­tri­ser ces conven­tions et leurs conver­sions est un pré­re­quis indis­pen­sable pour tra­vailler serei­ne­ment avec les don­nées géno­miques.

Pour aller plus loin et com­prendre l'implication des sys­tèmes de coor­don­nés sur la des­crip­tion de variant je vous invite à regar­der ceci :
https://​juke34​.github​.io/​c​o​o​r​d​i​n​a​t​e​_​s​y​s​t​e​m​s​/​v​a​r​i​a​nts

Un immense mer­ci à Guillaume, Samuel et Aze­rin pour leur relec­ture atten­tive de l'article.

P.S : l'IA a été uti­li­sé pour for­ma­ter le texte et cor­ri­ger les fautes d'orthographes.