Parser PHP arbre phylogénétique type Newick

Version imprimable

Voir 40 message(s) de cette discussion en une page

10/07/2012, 16h25
fourmizen

Parser PHP arbre phylogénétique type Newick

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

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

Code:

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:

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;

10/07/2012, 17h19
gene69

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.

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:

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:

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
        )
 
)

10/07/2012, 18h59
gene69

c'est pas des "si fin" c'est des si ... sinon si .... sinon si.
dsl.
10/07/2012, 19h03
gene69

c'est aussi parce que j'ai pas compris à quoi sert le ':'. Explique et on termine l'algo. c'est pour les sous groupes visiblement ?

je serai curieux de voir le résultat de ceci. j'ai toujours pas mon compilateur sous la main.

Code:

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
function ParseTree($arbre,$position,&$dejaLu){
		$max_leng = strlen($arbre);
		$tampon = '';
		$resultat=array();
		$nomGroupe = false; // a vrai lorsque ce qui suit peut être un nom de sous groupe.
		while( $position < $max_leng ){
			$tmp = $arbre[$position]; 
			if($tmp == '(') {
				$resultat[]= ParseTree( $arbre, $position+1, $dejaLu ); //passage par référence! 
				$position = $dejaLu;
 				$nomGroupe = true;
			}
			else 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?
			}
			else if($tmp == ',') {
    				if ( $nomGroupe ){
				 $last = array_pop( $resultat);
  				 $resultat[$tampon] = $last;
				}
				else {
				// on a fini de lire le fils de gauche
				$resultat[]=$tampon;
				$tampon = '';
				}
				$nomGroupe = false;
			} else { 
				$tampon .= $tmp;
				$nomGroupe = false;
			}
			$position++;
		}
		return $resultat;
	}

en fait c'était pas terrible.

3e essai.

Code:

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
52
53
 
function ParseTree($arbre,$position,&$dejaLu){
	$max_leng = strlen($arbre);
	$tampon = '';
	$resultat=array();
	$nomGroupe = 0; // a 2 lorsque ce qui suit peut être un nom de sous groupe.
	while( $position < $max_leng ){
		$tmp = $arbre[$position]; 
		if( $tmp == '(') {
			$resultat[]= ParseTree( $arbre, $position+1, $dejaLu ); //passage par référence! 
			$position = $dejaLu;
 			$nomGroupe = 1; //d'apres wikipedia, on peut avoir un nom de groupe apres une ), dans ce cas pas de ,
		}
		else if ($tmp == ')') {
			//on a fini de lire le fils de droite
			if ( $nomGroupe == 2 ){
				$last = array_pop($resultat);
				$resultat[$tampon]=$last;
				return $resultat;
			}
			else {
				$resultat[]=$tampon;
				$dejaLu= $position;
				return $resultat; //c'est la virgule qui sépare les fils?
			}
		}
		else if( $tmp == ',' ) {
			// on a fini de lire le fils de gauche
    			if ( $nomGroupe == 2 ){
				$last = array_pop($resultat);
				$resultat[$tampon]=$last;
    			}
    			else { 
 	 			if ( $nomGroupe == 1 ){ //une virgule tout de suite après une ')'
    		 			$nomGroupe = 0;
		 		}
		 		else { // un gros doute sur cette partie.
 	 	 	 	// $nomGroupe  == 0  // avec un doute 
				$resultat[]=$tampon; // devrait être vide ???
				$tampon = '';
		 		}
		}
		else { 
			$tampon .= $tmp;
			if ( $nomGroupe == 1 ){
				$nomGroupe == 2;
			}
		}
	$position++;
	}
 
	return $resultat;
}

mmm je pense que ton dernier code s'éloigne un peu de ce que je veux puisqu'il donne cela :

Code:

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
Array
(
    [0] => Array
        (
            [0] => Array
                (
                    [0] => Array
                        (
                            [0] => 1:0.01
                            [1] => 2:0.01
                        )
 
                    [1] => Array
                        (
                            [0] => Array
                                (
                                    [0] => 3:0.03
                                    [1] => 4:0.03
                                )
 
                            [1] => Array
                                (
                                    [0] => 5:0.02
                                    [1] => 19:0.02
                                )
 
                            [2] => :0.01:0.02
                        )
 
                    [2] => :0.04:0.01
                )
 
            [1] => Array
                (
                    [0] => 7:0.13
                    [1] => 20:0.13
                )
 
            [2] => :0.33:0.25
        )
 
    [1] => :0.096:0.46
)

Idéalement au point ou on en est ils faudrait l'étape d'avant sans les ) avant les :

Code:

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
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
)

En fait l'objectif final final est d'obtenir un array du genre suivant avec pour chaque niveau la distance (qui est exprimée par les :0.25) et la liste des ID du groupe (et pour les groupes de plus haut niveau tous les ID qu'il existe en dessous) :

Code:

1
2
3
4
5
6
7
8
9
10
11
12
Array
(
    [0] => Array
    (
        [0] =>0.25
        [1] => Array
        (
            [0] => 7
            [1] => 20
        )
    )
)

Je ne sais pas si j'ai été très clair auquel cas dis le moi ! :ccool:

aaaaah j'ai corrigé les if en ifelse et effectivement tout marche bien ! Ton premier code était le bon : bravo ;)

On a donc ceci :

Code:

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
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
)

Ce qu'il faudrait donc maintenant faire (peut être une autre fonction à partir de cet output) c'est de créer des groupes car ceci est la représentation d'un dendrogramme en fait :

http://hpics.li/d70ffe8
http://hpics.li/d70ffe8

Et il me faudrait sa représentation en array avec le plus grand groupe qui comprends tous les IDs puis 2 groupes répartis avec les distances (ts les chiffres précédés par des :) du haut vers le bas (donc du grand groupe aux petits groupes). J'ai commencé à écrire quelque chose mais j'étais bloqué au fait qu'à chaque fois il fallait itérer en allant plus loin dans l'array...

j'ai trouvé une option pour générer mes arbres de cette manière dans un fichier texte qui représente beaucoup plus l'aspect de l'Array dont j'ai besoin au final. Peut être serait-il plus facile d'utiliser cela que l'arbre de Newick précédemment en adaptant le code que tu as écrit :

Code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
+ 9 [1.16, 1.16]
	+ 6 [0.19, 0.19]
		+ 4 [0.06, 0.06]
			+ 2 [0.01, 0.01]
				* 1
				* 2
			+ 2 [0.02, 0.02]
				* 5
				* 19
		+ 2 [0.03, 0.03]
			* 3
			* 4
	+ 3 [1.06, 1.06]
		* 6
		+ 2 [0.13, 0.13]
			* 7
			* 20

Avec un array en output du style (je suis descendu que jusqu'au 3eme niveau hein ^^) :

Code:

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
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
Array(
	[0] => Array (
		[0] => Array (
			[Nombre_Appreannts] => 9
			[Distance] => 1.16
			[id] => Array (
				[0] => 1
				[1] => 2
				[2] => 5
				[3] => 19
				[4] => 3
				[5] => 4
				[6] => 6
				[7] => 7
				[8] => 20
			)
		)
	) 
	[1] => Array (
		[0] => Array (
			[Nombre_Appreannts] => 6
			[Distance] => 0.19
			[id] => Array (
				[0] => 1
				[1] => 2
				[2] => 5
				[3] => 19
				[4] => 3
				[5] => 4
			)
		)
		[1] => Array (
			[Nombre_Appreannts] => 3
			[Distance] => 1.06
			[id] => Array (
				[0] => 6
				[1] => 7
				[2] => 20
			)
		)
	) 
	[2] => Array (
		[0] => Array (
			[Nombre_Appreannts] => 4
			[Distance] => 0.06
			[id] => Array (
				[0] => 1
				[1] => 2
				[2] => 5
				[3] => 19
			)
		)
		[1] => Array (
			[Nombre_Appreannts] => 2
			[Distance] => 0.03
			[id] => Array (
				[0] => 3
				[1] => 4
			)
		)
		[2] => Array (
			[Nombre_Appreannts] => 2
			[Distance] => 0.13
			[id] => Array (
				[0] => 7
				[1] => 20
			)
		)
		[3] => Array (
			[Nombre_Appreannts] => 1
			[Distance] => Alone
			[id] => Array (
				[0] => 6
			)
		)
	) 
)

11/07/2012, 12h56
gene69

je regarderai quand j'aurai un peu plus de temps parce que la version 3 donne pas du tout le résultat escompté. c'est ça de tout faire de tête.
11/07/2012, 14h29
ascito

petite question :

(1:0.01,2:0.01):0.04

est-ce 0.04 le résultat d'une paire (1:0.01,2:0.01)

ou est-ce (1:0.01,2:0.01) le résultat d'une clé 0.04

?

Note : à y regarder de plus prêt il semble bien que le résultat se compose toujours à gauche d'une paire et à droite d'une valeure...
11/07/2012, 15h21
fourmizen

Super ! Merci pour votre aide.

en fait le 0.04 c'est la distance à l'échelon suivant. La dernière structure d'arbre que j'ai proposée est plus facile à comprendre.

~~on était à un = de ce que je voulais faire. pff.~~ en fait, avec une classe c'est plus simple.

Code:

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
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
 
$arbre = new Newik( '((((1:0.a1,2:a2)3:0.a3,((4:0.b1,5:0.b2)6:0.b3,(7:0.c1,8:0.c2)9:0.c3)10:0.bc3)11:0.abc3,(12:0.d1,13:0.d2):0.d3)14:0.abcd3,15:0.e2)');
 
$foobar = null;
echo '<pre>';
print_r($arbre->parse($arbre));
 
 
Class Newik {
 
	protected $arbre;
	private $position;
	private $max_leng;
 
 
	function __construct($arbre){
		$this->arbre = $arbre;
		$this->init();
	}
 
	function init(){
		$this->position=0;
		$this->max_leng = strlen($this->arbre);
	}
 
	function debug($msg, $tampon, $flag){
		echo $this->arbre,"\n";
		$turing = str_repeat('.',$this->max_leng)."\n";
		$turing[$this->position]= "^";
		echo $turing;
		echo $msg,' ',$this->arbre[$this->position],' position:',$this->position,' tampon:',$tampon,' flag:',$flag,"\n\n";
	}
 
	function appendChild(&$resultat, $flag,$tampon){
//		$this->debug('naming ', $tampon, $flagNomGroupe );
		if ( $flag == 2 ){
			$last = array_pop($resultat);
			$resultat[$tampon]=$last;
		}
		else {
			$resultat[]=$tampon;
		}		
	}
 
	function parse(){
	//	$this->debug(' begin ', $arbre, $position );
		$tampon = '';
		$resultat=array();
		$flagNomGroupe = 0; // a 2 lorsque ce qui suit peut être un nom de sous groupe.
		while( $this->position < $this->max_leng ){
 
			$tmp = $this->arbre[$this->position]; 
			if( $tmp == '(' ) {
				//$this->debug('open ', $tampon,$flagNomGroupe );
				$this->position++;
				$resultat[]= $this->parse(); //passage par référence! 
				$flagNomGroupe = 1; //d'apres wikipedia, on peut avoir un nom de groupe apres une ), dans ce cas pas de ,
			}
			else if ($tmp == ')') {
				//on a fini de lire le fils de droite
				$this->appendChild($resultat, $flagNomGroupe, $tampon);
				//$this->debug('closing ', $tampon,$flagNomGroupe );
				return $resultat; 
			}
			else if( $tmp == ',' ) {
				// on a fini de lire le fils de gauche
				$this->appendChild($resultat, $flagNomGroupe, $tampon);
				if ( $flagNomGroupe == 1 ){ //une virgule tout de suite après une ')'
						$flagNomGroupe = 0;
				}
				$tampon = '';
			}
			else {
				$tampon .= $tmp;
				if ( $flagNomGroupe == 1 ){
					$flagNomGroupe = 2;
				}
				//debug('concat ',  $tampon, $flagNomGroupe );
			}
			$this->position++;
		}
		return $resultat;
	}
}

Ok alors comme j'utilise cakephp comme framework, la fonction __construct foire un peu tout. J'ai un apercu d'array mais il manque des données car la class ne doit pas avoir l'a taille totale de l'arbre vu que construct n'est pas pris en compte (et qu'il lance la fonction init()).

Je reçois ça pour l'arbre suivant :

Code:

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
Array
(
    [0] => Array
        (
            [6:0.84] => Array
                (
                    [:0.59] => Array
                        (
                            [:0.05] => Array
                                (
                                    [:0.05] => Array
                                        (
                                            [0] => 1:0.01
                                            [1] => 2:0.01
                                        )
 
                                    [:0.04] => Array
                                        (
                                            [0] => 5:0.02
                                            [1] => 19:0.02
                                        )
 
                                )
 
                            [:0.08] => Array
                                (
                                    [0] => 3:0.03
                                    [1] => 4:0.03
                                )
 
                        )
 
                    [:0.57] => Array
                        (
                            [0] => 7:0.13
                            [1] => 20:0.13
                        )
 
                )
 
        )
 
)

Code:

(((((1:0.01,2:0.01):0.05,(5:0.02,19:0.02):0.04):0.05,(3:0.03,4:0.03):0.08):0.59,(7:0.13,20:0.13):0.57):0.14,6:0.84);

La je pense que sous peu je pourrais reprendre la main pour formater tout ça mais comment éviter la fonction construct ?

13/07/2012, 19h03
gene69
c'est embétant parce que je ne connais pas cakePHP.

s'il te faut un constructeur qui ne fait rien, pas grave.
Code:

1 2 3 4 5 6 7 8 9 //function __construct(){} function init($arbre){ $this->arbre = $arbre; $this->position=0; $this->max_leng = strlen($this->arbre); }
tu peux pas avoir des objets qui font des traitements et des objets qui sont spécifique à CakePHP qui servent à manipuler des objets qui font des traitements ? bizarre !
13/07/2012, 19h10
gene69

l'inconveniant de la méthode c'est que si l'objet n'est pas passé par init() (ou ce que tu veux !!!! ) ton objet ne sera pas initialisé. Comme dans la vie d'un objet ya que le constructeur qui est garanti (et p'tre le destructeur) c'est pas top, faudra être rigoureux.

t'a du faire un truc quand même parce que c'est le constructeur qui initialise "le ruban" (St Allan, priez pour moi), je veux dire $this->arbre.
13/07/2012, 19h16
fourmizen
en fait je pense que dans cakePHP quand on fait appel à une classe il a une fonction qui fait automatiquement office de construct. J'ai écrit ça pour l’appeler :
Code:

1 2 $arbre = new $this->Newick(substr($file_content, 0, -1)); $TreeParse = $arbre->parse($arbre);
13/07/2012, 20h07
gene69

le $arbre->parse($arbre) ne fait pas trop de sens pour moi parce que dans ma version parse() ne prend pas d'argument et comme dans une methode d'un objet $arbre, $arbre se connait lui même ($this) ça ne fait fait pas trop de sens de le mettre en parametre là.

Par hazard tu as quoi comme code?

S'il y a de la magie, c'est possible si tu déclares que Newick est une classe dérivée d'une classe CakePHP, il peut y en avoir un peu.

On arrive à la limite de mes compétences. Peut-être devrait tu relancer un nouveau sujet sur le thème "comment integrer une classe personnelle dans CakePHP" si aucune personne connaissant bien CakePHP n'intervient sur ce fil...

Voir 40 message(s) de cette discussion en une page