Parser PHP arbre phylogénétique type Newick

**fourmizen** · 10/07/2012, 15h25

Bonjour,
dans le cadre de mes études, j'aimerais pouvoir lire un arbre phylogénétique du type suivant (Newick) :

((((1:0.01,2:0.01):0.04,((3:0.03,4:0.03):0.01,(5:0.02,19:0.02):0.02):0.01):0.33,(7:0.13,20:0.13):0.25):0.09,6:0.46)

J'ai essayé de trouver un parser pour le transformer en array pour traitement ultérieur mais il ne semble pas en exister en PHP.

Une solution à mis chemin se trouve peut être dans ce code qui permet de parser les parenthèses... : http://stackoverflow.com/questions/7...utput-to-array

L'un d'entre vous aurait-il un code perso ou pourrait-il me proposer un premier chunk sur lequel travailler ou m'aider à adapter le code du lien ci dessus ?

Merci bien,
Raphaël

**gene69** · 10/07/2012, 16h02

la grammaire de ton arbre à l'air d'etre simple. du coup un truc comme ça pourrait marcher

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
(
 (
  (
   (1:0.01,2:0.01):0.04,
   (
     (3:0.03,4:0.03):0.01,
     (5:0.02,19:0.02):0.02
   ):0.01
  ):0.33,
  (7:0.13,20:0.13):0.25
 ):0.09,
6:0.46)

Code speudocode php :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
$arbre='((((.......)....';
$foobar = 0;

read($arbre, 0, $foobar );

function read($arbre,$position, &$dejaLu ){
$max_leng = strlen($arbre);
$tampon = '';
$resultat=array();
while( $position < $max_leng ){
 $tmp = $arbre[$position]; 
 si $tmp == '(' alors 
    $resultat[]= read( $arbre, $position+1, $dejaLu ) //passage par référence! 
    $position = $dejaLu;
 si  $tmp == ')' alors 
     //on a fini de lire le fils de droite
     $resultat[]=$tampon;
     $dejaLu= $position;
     retourner $resultat; //c'est la virgule qui sépare les fils?
 si $tmp == ',' alors
     // on a fini de lire le fils de gauche
     $resultat[]=$tampon;
     $tampon = '';
 sinon 
     $tampon .= $tmp;
 fin
 $position++; //pas sur de ça.
}
//normalement on ne passe jamais ici
afficher "erreur ?";
retourner $resultat;

**gene69** · 10/07/2012, 16h19

je viens de lire la description dans wikipedia, mon code ne gère pas ce que vous appelez les sous-groupes vous biologistes.

c'est pas si compliqué que ça a faire... je te laisse faire, mais ça complique le code parce qu'il faut traiter deux cas, ")," et ")" parenthèse fermante avec ou sans virgure, verrait bien 2 flags pour ajouter ça et des bidouilles pour mettre mettre le nom du "sous-groupe" à la place de l'index automatique.

je suis sur que quelqu'un de fort arrivera à écrire la regex recursive qui va bien.

**fourmizen** · 10/07/2012, 17h27

Super ! Merci beaucoup pour ce message rapide qui me fournit une bonne première base.

J'ai un peu repris le code pour qu'il fonctionne dans mon appli et ca donne ça (riende changé en profondeur) :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
	function ParseTree($arbre,$position,&$dejaLu){
		$max_leng = strlen($arbre);
		$tampon = '';
		$resultat=array();
		while( $position < $max_leng ){
			$tmp = $arbre[$position]; 
			if($tmp == '(') {
				$resultat[]= ParseTree( $arbre, $position+1, $dejaLu ); //passage par référence! 
				$position = $dejaLu;
			}
			if ($tmp == ')') {
				//on a fini de lire le fils de droite
				$resultat[]=$tampon;
				$dejaLu= $position;
				return $resultat; //c'est la virgule qui sépare les fils?
			}
			if($tmp == ',') {
				// on a fini de lire le fils de gauche
				$resultat[]=$tampon;
				$tampon = '';
			} else { 
				$tampon .= $tmp;
			}
			$position++;
		}
		return $resultat;
	}

Ça s'approche déjà de la première étape de transformation par contre dans le résultat un caractère apparait et je ne comprends pas pourquoi : on a par exemple du '(:0.04' au lieu d'avoir ':0.04' (cf print ci dessous).

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
Array
(
    [0] => Array
        (
            [0] => Array
                (
                    [0] => Array
                        (
                            [0] => Array
                                (
                                    [0] => 1:0.01
                                    [1] => 2:0.01
                                )
 
                            [1] => (:0.04
                            [2] => Array
                                (
                                    [0] => Array
                                        (
                                            [0] => 3:0.03
                                            [1] => 4:0.03
                                        )
 
                                    [1] => (:0.01
                                    [2] => Array
                                        (
                                            [0] => 5:0.02
                                            [1] => 19:0.02
                                        )
 
                                    [3] => (:0.02
                                )
 
                            [3] => (:0.01
                        )
 
                    [1] => (:0.33
                    [2] => Array
                        (
                            [0] => 7:0.13
                            [1] => 20:0.13
                        )
 
                    [3] => (:0.25
                )
 
            [1] => (:0.09
            [2] => 6:0.46
        )
 
)