- Le blog participatif de bioinformatique francophone depuis 2012 -

Automatiser le parcours et la manipulation d’arbres phylogénétiques avec le module Bio.Phylo de BioPython

La géno­mique com­pa­ra­tive per­met d'étudier l'évolution d'organismes par com­pa­rai­son de leur génome. La repré­sen­ta­tion de la proxi­mi­té entre les orga­nismes, élé­ment essen­tiel de la géno­mique com­pa­ra­tive, repose sur des arbres phy­lo­gé­né­tiques. Mais com­ment mani­pu­ler ces arbres faci­le­ment ? Quand il n’y en a qu’un, pas de pro­blème : on uti­lise un visua­li­sa­teur comme ceux pro­po­sés dans l’article sur les arbres phy­lo­gé­né­tiques. Cepen­dant, avec plu­sieurs cen­taines ou mil­liers d’arbres, les trai­te­ments manuels doivent être rem­pla­cés par des rou­tines. Pour cela, des boîtes à outils pour tra­vailler avec l’information phy­lo­gé­né­tique sont dis­po­nibles et lar­ge­ment uti­li­sées : Ape de R, Bio::Phylo (Vos et al, 2011) de Bio­Perl, … En Python, plu­sieurs librai­ries ont été conçues pour la phy­lo­gé­nie : PyCogent (Knight et al, 2007), Den­dro­Py (Suku­ma­ran & Hol­der, 2010) , ETE (Huer­ta-Cepas et al, 2010), p4 (Fos­ter, 2003) et Bio.Phylo (Tale­vich et al, 2012). Cette der­nière, contrai­re­ment aux autres, a pour objec­tif d’être géné­ra­liste, facile à uti­li­ser et com­pa­tible avec d'autres pro­grammes, per­met­tant ain­si le déve­lop­pe­ment rapide de scripts pour l’automatisation de la mani­pu­la­tion des arbres. Tota­le­ment inté­gré à Bio­Py­thon et codé en Python, ce module n’a pas besoin de librai­rie sup­plé­men­taire et fonc­tionne sur des implé­men­ta­tions alter­na­tives de Python comme Jython ou Pypy.

biopython
Logo offi­ciel de Bio­Py­thon

Ce module est de plus en plus uti­li­sé grâce au déve­lop­pe­ment conti­nu de ses fonc­tion­na­li­tés et de sa docu­men­ta­tion. Ce module a, par exemple, ser­vi dans une étude de phy­lo­gé­no­mie micro­bienne (Bei­ko, 2010) où les topo­lo­gies de plus de 100 000 arbres ont été per­mu­tées grâce à des rou­tines. Pour ma part, j’ai uti­li­sé Bio.Phylo pour com­pa­rer des vitesses d’évolution entre des familles de gènes, récu­pé­rer des familles mono­phy­lé­tiques, récon­ci­lier des arbres de familles de gènes avec un arbre d’espèces …

Le module Bio.Phylo donne accès à des méthodes pour la mani­pu­la­tion et l’analyse simple d’arbres phy­lo­gé­né­tiques, comme la recherche et le par­cours d’arbres, l’extraction d’informations basiques et leur modi­fi­ca­tion. Ces méthodes peuvent être faci­le­ment uti­li­sées pour des rou­tines dans des work­flows bio­in­for­ma­tiques grâce à la docu­men­ta­tion du module (wiki et les exemples d'utilisation, manuel Bio­Py­thon et article de Tale­vich et al, 2012). Contrai­re­ment aux méthodes d’entrées/sorties et de visua­li­sa­tion des arbres, les méthodes pour mani­pu­ler et par­cou­rir les arbres sont peu docu­men­tées et ne sont sou­vent pas illus­trées. Ces lacunes rendent le déve­lop­pe­ment des rou­tines un peu com­plexe. Le but de cet article est donc de com­plé­ter la docu­men­ta­tion exis­tante afin de faci­li­ter votre tra­vail de déve­lop­pe­ment. Pour illus­trer les méthodes, je vais uti­li­ser l’arbre sui­vant :

ex_arbre

L’arbre est enre­gis­tré dans le fichier "tree" sous le for­mat Newick avec la chaine sui­vante : (((H:.1,G:.2)5:.5,(((F:.1,E:.2)7:.3,D:.1)6:.4,C:.1)4:.5)3:1.5,(B:.1,A:.1)2:2)1 ;

Objets pour gérer les arbres dans Bio.Phylo

Les arbres dans le module sont enre­gis­trés en sui­vant la struc­ture :

structure

Ain­si, quand un arbre est créé, un objet

 est créé. Cet objet pointe vers un objet

 cor­res­pon­dant à la racine, que l’arbre soit raci­né ou pas. Cet objet

 contient les infor­ma­tions liées à chaque clade (ou sous-arbre démar­rant à la branche cou­rante et ter­mi­nant avec les branches ter­mi­nales liées à ce sous-arbre) ain­si que des réfé­rences vers les clades fils. La struc­ture d’enregistrement des arbres dans Bio.Phylo repose sur l’hypothèse de topo­lo­gie d’arbre et ne per­met pas une topo­lo­gie de type réseaux avec plus d’un parent pour un clade.

Ain­si, les objets de la classe

 ont comme attri­buts :


  • name : Nom

  • id : Iden­ti­fiant

  • root : Réfé­rence vers un objet
    Clade cor­res­pon­dant à la racine

  • weight : Poids

  • roo­ted : Boo­léen indi­quant si l’arbre est raci­né ou pas

Ces attri­buts sont acces­sibles (en lec­ture et écri­ture) direc­te­ment. Les attri­buts des ins­tances de la classe

 sont :


  • name : Nom

  • branch_​length 
    : Lon­gueur de la branche condui­sant au clade

  • clades 
    : Liste de réfé­rences vers les clades fils

  • confi­dence 
    : Confiance

  • com­ment 
    : Com­men­taire

  • width 
    : Lar­geur de la branche pour la visua­li­sa­tion

  • _​color 
    : Cou­leur pour la visua­li­sa­tion

Pour sto­cker l’information sup­plé­men­taire spé­ci­fiques à cer­tains for­mats de fichiers (Phy­loXML et Newick, par exemple), des sous-modules offrent des classes sup­plé­men­taires qui héritent des classes

 et

. Je ne vais pas pré­sen­ter ici les spé­ci­fi­ci­tés de ces sous-modules.

Création d’arbres dans Bio.Phylo

Les arbres dans Bio.Phylo sont géné­ra­le­ment crées par lec­ture de fichiers dans dif­fé­rents for­mats pos­sibles : Newick, NEXUS, Phy­loXML, NeXML, Com­pa­ra­tive Data Ana­ly­sis Onto­lo­gy (CDAO). Une inter­face de pro­gram­ma­tion (API) uni­fiée per­met de prendre en charge tous les for­mats d’entrée et ren­voie un objet

, iden­tique quel que soit le for­mat d’entrée.

La méthode 

 per­met de lire un arbre dans le fichier don­né et le ren­voie. Le for­mat du fichier cor­res­pond au deuxième argu­ment des méthodes pré­cé­dentes.

Une erreur est géné­rée lorsque le fichier pas­sé en argu­ment contient plus d’un arbre ou pas d’arbre. Cepen­dant, les arbres conte­nus dans un même fichier peuvent être char­gés avec la méthode

 :

Il est aus­si pos­sible d’utiliser direc­te­ment des chaines de carac­tères pour char­ger un arbre avec

 :

Des sous-modules spé­ci­fiques à chaque for­mat de fichiers (Phy­loXM­LIO, NeXM­LIO, Newi­ckIO, Nexu­sIO, CDAOIO) per­mettent de char­ger les arbres et toutes les infor­ma­tions spé­ci­fiques à chaque for­mat.

Un arbre peut aus­si être créé à par­tir d’un clade avec

. L’arbre obte­nu cor­res­pond alors au sous-arbre démar­rant au clade sélec­tion­né, avec ses des­cen­dants.

tree2

 Exportation des arbres

La méthode

 per­met d’exporter le (ou les) arbre(s) dans un fichier ou une chaine de carac­tères

Pour conver­tir des fichiers entre les for­mats Newick, Nexus, Phy­loXML, …, on uti­lise la méthode 

Les arbres peuvent aus­si être expor­tés vers d’autres for­mats pour être uti­li­sables dans d’autres modules Python ou logi­ciels comme R. Ain­si, dans le wiki, sont pré­sen­tées des méthodes pour expor­ter pour Ape avec RPy2, Den­dro­Py ou PyCogent, mais aus­si en matrice Num­py.

Visualisation des arbres

Dans Bio.Phylo, la visua­li­sa­tion des arbres peut se faire en :

  • Chaine de carac­tères avec la hié­rar­chie com­plète de l’objet

  • Den­do­gramme simple en ASCII

  • Phy­lo­gramme, si les libraires mat­plot­lib ou PyLab sont ins­tal­lées

  • Cla­do­gramme, si Gra­ph­viz, PyDot ou PyGra­ph­viz, Net­workX et mat­plot­lib ou PyLab ins­tal­lés

Les repré­sen­ta­tions peuvent être modi­fiées avec l’ajout de cou­leurs par exemple, mais aus­si avec des librai­ries comme mat­plot­lib ou PyLab. Les méthodes per­met­tant ces modi­fi­ca­tions sont bien décrites dans le tuto­riel de Bio­Py­thon ou le wiki.

 Récupération d’informations sur l’arbre et sa topologie

La topo­lo­gie d’un arbre ou d’un sous-arbre peut être inter­ro­gée avec plu­sieurs méthodes :


  • is_​monophyletic 
    teste si la liste des cibles four­nies forme un sous-clade com­plet dans l’arbre à par­tir duquel la méthode est appe­lée. Cette méthode teste donc s’il existe un clade tel que ces nœuds ter­mi­naux soient exac­te­ment les cibles. Si c’est le cas, la méthode ren­voie le clade cor­res­pon­dant à l'ancêtre com­mun le plus proche, ou Faux sinon.

  • is_​bifurcating teste si un arbre est stric­te­ment bifur­cant, c’est-à-dire que tous les nœuds ont 0 ou 2 enfants. La racine peut cepen­dant avoir 3 des­cen­dants, l’arbre sera tou­jours consi­dé­ré comme bifur­cant.

La posi­tion d’un clade dans l’arbre est inter­ro­geable avec :


  • is_​terminal teste si un clade est ter­mi­nal. C’est équi­valent à
    if c1.clades : … qui teste si un clade <em>c1</em> a des des­cen­dants

  • is_​preterminal teste si tous les des­cen­dants directs sont ter­mi­naux et ren­voie Faux si au moins une des des­cen­dants directs ne l’est pas

  • is_​semipreterminal 
    teste si au moins un des des­cen­dant est ter­mi­nal et ren­voie Faux si tous les des­cen­dants directs ne le sont pas ou si le clade est ter­mi­nal

  • if c1 in c2.clades :… teste si un clade <em>c1</​em> est le des­cen­dant direct dun clade <em>c2</​em>

  • is_​parent_​of 
    teste si une cible est un des­cen­dant (pas obli­ga­toi­re­ment direct) du clade à par­tir de laquelle la méthode est appe­lée.

Les nœuds internes et externes d’un clade ou de l’arbre entier sont récu­pé­rés avec les méthodes

 et

, qui ren­voient une liste avec des réfé­rences sur les clades cor­res­pon­dants. Simi­lai­re­ment, la méthode

 compte le nombre de nœuds ter­mi­naux au sein de l’arbre.

Avec la struc­ture d’arbres dans Bio.Phylo, les réfé­rences vers les parents ne sont pas sto­ckées pour chaque clade. On peut uti­li­ser la méthode

 (décrite par la suite) pour retrou­ver le lien parent-fils avec la méthode sui­vante :

Parcours et navigation dans les arbres

Parcours des arbres

Pour par­cou­rir l’arbre phy­lo­gé­né­tique, il faut par­tir de la racine avec

, qui pointe vers un objet

. On peut ensuite par­cou­rir les clades de l’arbre en pro­fon­deur, en visi­tant les clades fils avec 

 dans une méthode récur­sive, par exemple :

Le che­min entre deux clades parentes peut être récu­pé­ré avec la méthode

. Celle-ci ren­voie la liste des clades entre la racine ou le clade cou­rant et un clade cible, en ter­mi­nant par le clade cible et en excluant le clade racine. Cepen­dant, le che­min ren­voyé est tou­jours un che­min en pro­fon­deur. Ain­si, si le clade cou­rant n’est pas parent du clade cible, la méthode ne ren­voie rien. La liste des clades entre deux clades cibles, pas obli­ga­toi­re­ment avec un che­min des­cen­dant, est acces­sible avec la méthode 

Recherche dans les arbres

Pour recher­cher des nœuds au sein de l’arbre ou dans des sous-clades, il existe 3 trois méthodes (

,

,

) qui reposent toutes les trois sur la même défi­ni­tion, avec les attri­buts :

  • Tar­get ( None par défaut) : spé­ci­fie les carac­té­ris­tiques à recher­cher, comme
    • Une ins­tance de
      Clade qui pour­rait cor­res­pondre par iden­ti­té, pour recher­cher, par exemple, la posi­tion d’un clade dans un arbre
    • Une chaine de carac­tères qui puisse cor­res­pondre à une repré­sen­ta­tion en chaine de carac­tères d’un attri­but de
      Clade (nom, par exemple)
    • Une classe ou un type pour lequel tout élé­ment de l’arbre du même type pour­rait cor­res­pondre
    • Un dic­tion­naire où les clés sont des attri­buts de
      Clade (nom, lon­gueur, …) et les valeurs sont tes­tées aux attri­buts cor­res­pon­dant de chaque élé­ment de l’arbre
    • Une fonc­tion pre­nant un argu­ment et ren­voyant Vrai ou Faux
  • Ter­mi­nal ( None, par défaut) : valeur boo­léenne pour ou contre les nœuds ter­mi­naux.

    • True 
      : recherche uni­que­ment des nœuds ter­mi­naux

    • False 
      : exclu­sion des nœuds ter­mi­naux

    • None 
      : recherche à la fois des nœuds ter­mi­naux et internes
  • Order ( preor­der, par défaut) : ordre de par­cours de l’arbre

    • preor­der : recherche selon un algo­rithme de recherche en pro­fon­deur

    • post­or­der : recherche selon un algo­rithme de recherche en pro­fon­deur où les nœuds fils pré­cèdent les parents

    • level : recherche selon un algo­rithme de recherche en lar­geur

La méthode

 cherche les élé­ments de l’arbre qui cor­res­pondent à la cible.

 fonc­tionne sur le même prin­cipe, mais retourne les objets

  cor­res­pon­dants. Ces méthodes ren­voient un objet ité­rable selon l’ordre défi­ni par

 et qui n’est pas néces­sai­re­ment le même ordre que celui d’apparition des élé­ments dans le fichier source. La méthode 

 ren­voie le pre­mier élé­ment trou­vé par

 ou

 , per­met­tant de tes­ter l’existence de l’élément « recher­ché » dans l’arbre et uti­li­sable dans une expres­sion condi­tion­nelle.

Pour obte­nir l’ancêtre com­mun le plus récent (MRCA, sous forme d’un objet

 ) de cibles don­nées, il faut uti­li­ser

. Si aucune cible n’est four­nie, la racine du clade à par­tir de laquelle la méthode est appe­lée est ren­voyée.

 Métriques

Plu­sieurs métriques sont acces­sibles sur les clades et les arbres. La méthode

 cal­cule la somme de toutes les lon­gueurs de branche de l’arbre. La dis­tance entre deux cibles, c’est-à-dire la somme des lon­gueurs des branches entre les cibles, est obte­nue avec la méthode

. Cette méthode est appe­lée à par­tir de l’arbre et si une seule cible est spé­ci­fiée, l’autre cible est défi­nie comme la racine de l’arbre. La méthode

 crée un map­ping des clades aux pro­fon­deurs. Le résul­tat est un dic­tion­naire où les clés sont tous les clades de l’arbre et les valeurs les dis­tances entre la racine et les clades. Par défaut, la dis­tance est la somme des lon­gueurs des branches mais il est pos­sible de comp­ter seule­ment de nombre de branches (avec

).

 Modifications d'arbres

Rotations

Les clades peuvent être triés selon le nombre de nœuds ter­mi­naux avec

. Par défaut, les clades les plus pro­fonds sont pla­cés en der­nier. L’inverse est pos­sible avec

. Cette méthode peut être appe­lée pour l’arbre com­plet ou pour un sous-arbre dont la racine cor­res­pond au clade cou­rant.

tree_ladderize
clade_ladderize

Raciner et reraciner

Pour raci­ner ou rera­ci­ner l’arbre, il existe deux méthodes. La pre­mière 

 rera­cine l’arbre au milieu cal­cu­lé entre les extré­mi­tés les plus dis­tantes de l’arbre. La seconde méthode 

 rera­cine l’arbre avec un clade out­group conte­nant l’ancêtre com­mun de l’out­group. Si l’out­group est iden­tique à la racine de l’arbre, il n’y a pas de chan­ge­ment. Si l’out­group est ter­mi­nal, un nou­veau clade racine bifur­cant est créé avec une branche de lon­gueur nulle vers l’out­group don­né. Dans les autres cas, le nœud interne à la base de l’out­group devient une racine tri­fur­quante pour l’arbre entier. Si la racine ori­gi­nale était bifur­cante, elle est éli­mi­née de l’arbre.

tree_root_at_midpoint
tree_root_with_outgroup_ca
tree_root_with_outgroup_terminal

Idéa­le­ment, il fau­drait que l’out­group soit mono­phy­lé­tique plu­tôt qu’un taxon seul. Ce n’est pas véri­fié auto­ma­ti­que­ment. Il est donc pré­fé­rable d’utiliser

 avant de rera­ci­ner un arbre.

Ajout de clades

Pour ajou­ter des des­cen­dants, on peut uti­li­ser la méthode

. Celle-ci ajoute n des­cen­dants (2 par défaut) à la racine ou au clade cou­rant. Les nou­veaux clades ont des lon­gueurs de branches défi­nies (1 par défaut) et le même nom que la racine du clade avec l’ajout d’un entier en suf­fixe.

tree_split
clade_split

Suppression de clades

La sup­pres­sion de clade peut se faire avec dif­fé­rentes méthodes.

 éli­mine un clade ter­mi­nal de l’arbre, soit à par­tir de la réfé­rence du clade, soit en cher­chant le clade avec

. Si le taxon est issu d’une bifur­ca­tion, le nœud cor­res­pon­dant est éli­mi­né et la lon­gueur de branche est ajou­tée à celle du nœud ter­mi­nal res­tant.

 sup­prime la cible de l’arbre, en liant les clades fils au clade parent de la cible.

 éli­mine tous les des­cen­dants de l’arbre, lais­sant seule­ment les nœuds ter­mi­naux. Les lon­gueurs de branches de la racine à chaque nœud ter­mi­nal sont conser­vées. Si une cible est four­nie, seuls les nœuds internes cor­res­pon­dant à la cible sont tou­chés.

tree_prune
tree_collapse
tree_collapse_all

Conclusion

Bio.Phylo est un module facile d’utilisation et per­met­tant le déve­lop­pe­ment rapide de rou­tines pour la mani­pu­la­tion et le par­cours d’arbres phy­lo­gé­né­tiques. Ce module est tou­jours en déve­lop­pe­ment et j’espère que de nou­velles fonc­tion­na­li­tés, comme la com­pa­rai­son d’arbres, vien­dront s’y gref­fer.

Mer­ci aux relec­teurs pour leurs com­men­taires : Clem_​, Dark­gi­lou, Waque­teu et Yoann M.

Références

Bei­ko (2010). Tel­ling the Whole Sto­ry in a 10,000-GenomeWorld. Biol Direct, 6:34.

Fos­ter (2003). p4 : A Python package for phy­lo­ge­ne­tics. [http://code. google​.com/​p​/​p​4​-​p​h​y​l​o​g​e​n​e​t​i​cs/].

Huer­ta-Cepas et al (2010). ETE : a python Envi­ron­ment for Tree Explo­ra­tion. BMC Bio­in­for­ma­tics. 11:24.

Knight et al (2007). PyCogent : a tool­kit for making sense from sequence. Genome Biol, 8(8):R171.

Suku­ma­ran & Hol­der (2010). Den­dro­Py : a Python libra­ry from phy­lo­ge­ne­tic com­pu­ting. Bio­in­for­ma­tics. 26(12) : 1569–1571.

Tale­vich et al (2012). Bio.Phylo : A uni­fied tool­kit for pro­ces­sing, ana­ly­zing and visua­li­zing phy­lo­ge­ne­tic trees in Bio­py­thon. BMC Bio­in­for­ma­tics, 13:209

Vos et al (2011). Bio : Phy­lo – phy­lo­in­for­ma­tic ana­ly­sis usiing Perl. BMC Bio­in­for­ma­tics, 12:63.




Commentaires

Laisser un commentaire