changer la racine d'un arbre (phylogénétique)

[invitef1f76460]

Bonjour,

Je représente un arbre phylogénétique (arbre non binaire) qui possède donc une racine, des noeuds internes et des feuilles
Alors voilà mon problème : je souhaite pouvoir changer de racine, c'est à dire que je choisirais un autre noeud comme étant la nouvelle racine. En phylogénie ce procédé est très apprécié ^^
Cependant, je n'arrive pas à comprendre comment se réorganise les noeuds.
Voici un exemple d'un logiciel qui fait très bien ce rerootage d'arbre ^^
Si quelqu'un pouvait m'indiquer un algo pour une publi qui en traite, je lui serais vraiment très reconnaissant !


Mélanie

A gauche, l'arbre avant le rerootage et à droite après avoir reooter la branche en bleu foncé.

Suppression des pièces jointes provenant d'un site d'hébergement. voici la procédure à suivre :

http://forums.futura-sciences.com/pr...ges-forum.html

pour la modération, Cram 64.
-----

[invite728b013d]

Bonjour à toutes et à tous,

Les images en provenance d'un site d'hébergement n'étant pas acceptées sur le site, voici la procédure à suivre :

http://forums.futura-sciences.com/pr...ges-forum.html

Cordialement,

Marc.

[JPL]

S'il n'y a pas de réponse ici tu n'auras qu'à le signaler et je transfèrerai le sujet en Biologie.

[invitef1f76460]

Désolée je n'avais pas fait attention.
Voici l'image qui correspond :

A gauche, l'arbre avant le rerootage et à droite après avoir reooter la branche en bleu foncé.






Edit : Alors j'avais commencé par mettre mon sujet dans la partie biologie mais on m'a dit que j'aurai peut être plus de réponse en algo ...

[A voir en vidéo sur Futura]

[invite068a575a]

Bonjour,

Je en suis pas sur de comprendre ton problème. SI c'est seulement un problème de représentation fais une recherche avec "phylogeny rooted unrooted" et tu trouveras des centaines de pages de présentation des différentes formes d'arbres et aussi de programmes. Je me servais souvent de Treeview (je vois qu'il existe toujours). En gros la plupart des programmes qui déterminent une phylogénie à partir d'alignements ne font que calculer des relations, n'importe quelle séquence (si ce sont des séquences) peut servir de racine, on peut dans ce cas préférer une représentation sans racine que tous les programmes de dessin d'arbres proposent.

Si tu fais l'hypothèse d'un ancêtre commun tu peux le désigner comme racine, tu peux aussi inclure dans ton alignement initial une séquence reliée mais que tu sais lointaine, par ex. dans un alignement de cyt C de mammifères inclure un cyt C de plante, il servira de racine.

De façon plus générale il y a une introduction claire et simple sur le site du NCBI, ou bien va voir la documentation de Phylip le paquet de programmes de Felsenstein.

Francis

[invitef1f76460]

En fait je ne parle pas de la représentation rooted ou unrooted. Mais à partir d'un arbre rooted, il est possible de changer la racine (mettre un cyt C de mammifères en tant que racine par exemple à la place du cyt C de plante).
J'ai regardé les infos des packages de Phylip : il y a bien une fonction "retree" qui permet de changer de racine mais il n'y a pas l'algorithme qui leur permet de faire ça. C'est bien ça que je recherche.
Je me suis mise à regarder le code (java car je code en java) des logiciels comme Archaepteryx (http://code.google.com/p/forester/ ou http://www.phylosoft.org/archaeopteryx/] qui se rapprochent de mon code mais je n'ai pas du tout l'habitude de regarder le code d'un si gros logiciel où les fonctions se croisent et se recroisent ...
Cependant en regardant le code je peux difficilement comprendre la logique, je ne fais que "copier-coller" en l'adaptant à mon code, mais cela ne fonctionne pas évidemment -_-'
Il me semble que la fonction qui permet de faire le reroot est celle ci :
J'ai compris certaines choses de cette fonction mais pas au point de pouvoir la faire marcher chez moi ...

/**
     * Places the root of this Phylogeny on the parent branch PhylogenyNode n.
     * The new root is always placed on the middle of the branch.
     * <p>
     * If the resulting reRooted Phylogeny is to be used any further, in most
     * cases the following three methods have to be called on the resulting
     * Phylogeny:
     * <ul>
     * <li>recalculateNumberOfExternalDescendants(boolean) <li>recalculateAndReset()
     * </ul>
     * <p>
     * (Last modified: 10/01/01)
     * 
     * @param n
     *            PhylogenyNode of this Phylogeny\
     */
    public void reRoot( final PhylogenyNode n ) {
        reRoot( n, -1 );
    }

    public void reRoot( final PhylogenyNode n, final double distance_n_to_parent ) {
        if ( isEmpty() || ( getNumberOfExternalNodes() < 2 ) ) {
            return;
        }
        setRooted( true );
        if ( n.isRoot() ) {
            return;
        }
        else if ( n.getParent().isRoot() ) {
            if ( ( n.getParent().getNumberOfDescendants() == 2 ) && ( distance_n_to_parent >= 0 ) ) {
                final double d = n.getParent().getChildNode1().getDistanceToParent()
                        + n.getParent().getChildNode2().getDistanceToParent();
                PhylogenyNode other;
                if ( n.getChildNodeIndex() == 0 ) {
                    other = n.getParent().getChildNode2();
                }
                else {
                    other = n.getParent().getChildNode1();
                }
                n.setDistanceToParent( distance_n_to_parent );
                final double dm = d - distance_n_to_parent;
                if ( dm >= 0 ) {
                    other.setDistanceToParent( dm );
                }
                else {
                    other.setDistanceToParent( 0 );
                }
            }
            if ( n.getParent().getNumberOfDescendants() > 2 ) {
                final int index = n.getChildNodeIndex();
                final double dn = n.getDistanceToParent();
                final PhylogenyNode prev_root = getRoot();
                prev_root.getDescendants().remove( index );
                final PhylogenyNode new_root = new PhylogenyNode();
                new_root.setChildNode( 0, n );
                new_root.setChildNode( 1, prev_root );
                if ( n.getBranchDataDirectly() != null ) {
                    prev_root.setBranchData( ( BranchData ) n.getBranchDataDirectly().copy() );
                }
                setRoot( new_root );
                if ( distance_n_to_parent >= 0 ) {
                    n.setDistanceToParent( distance_n_to_parent );
                    final double d = dn - distance_n_to_parent;
                    if ( d >= 0 ) {
                        prev_root.setDistanceToParent( d );
                    }
                    else {
                        prev_root.setDistanceToParent( 0 );
                    }
                }
                else {
                    if ( dn >= 0 ) {
                        final double d = dn / 2.0;
                        n.setDistanceToParent( d );
                        prev_root.setDistanceToParent( d );
                    }
                }
            }
        }
        else {
            PhylogenyNode a = n;
            PhylogenyNode b = null;
            PhylogenyNode c = null;
            final PhylogenyNode new_root = new PhylogenyNode();
            double distance1 = 0.0;
            double distance2 = 0.0;
            BranchData branch_data_1 = null;
            BranchData branch_data_2 = null;
            b = a.getParent();
            c = b.getParent();
            new_root.setChildNode( 0, a );
            new_root.setChildNode( 1, b );
            distance1 = c.getDistanceToParent();
            if ( c.getBranchDataDirectly() != null ) {
                branch_data_1 = ( BranchData ) c.getBranchDataDirectly().copy();
            }
            c.setDistanceToParent( b.getDistanceToParent() );
            if ( b.getBranchDataDirectly() != null ) {
                c.setBranchData( ( BranchData ) b.getBranchDataDirectly().copy() );
            }
            if ( a.getBranchDataDirectly() != null ) {
                b.setBranchData( ( BranchData ) a.getBranchDataDirectly().copy() );
            }
            // New root is always placed in the middle of the branch:
            if ( a.getDistanceToParent() == PhylogenyDataUtil.BRANCH_LENGTH_DEFAULT ) {
                b.setDistanceToParent( PhylogenyDataUtil.BRANCH_LENGTH_DEFAULT );
            }
            else {
                if ( distance_n_to_parent >= 0.0 ) {
                    final double diff = a.getDistanceToParent() - distance_n_to_parent;
                    a.setDistanceToParent( distance_n_to_parent );
                    b.setDistanceToParent( diff >= 0.0 ? diff : 0.0 );
                }
                else {
                    final double d = a.getDistanceToParent() / 2.0;
                    a.setDistanceToParent( d );
                    b.setDistanceToParent( d );
                }
            }
            b.setChildNodeOnly( a.getChildNodeIndex( b ), c );
            // moving to the old root, swapping references:
            while ( !c.isRoot() ) {
                a = b;
                b = c;
                c = c.getParent();
                b.setChildNodeOnly( a.getChildNodeIndex( b ), c );
                b.setParent( a );
                distance2 = c.getDistanceToParent();
                branch_data_2 = c.getBranchDataDirectly();
                c.setDistanceToParent( distance1 );
                c.setBranchData( branch_data_1 );
                distance1 = distance2;
                branch_data_1 = branch_data_2;
            }
            // removing the old root:
            if ( c.getNumberOfDescendants() == 2 ) {
                final PhylogenyNode node = c.getChildNode( 1 - b.getChildNodeIndex( c ) );
                node.setParent( b );
                if ( ( c.getDistanceToParent() == PhylogenyDataUtil.BRANCH_LENGTH_DEFAULT )
                        && ( node.getDistanceToParent() == PhylogenyDataUtil.BRANCH_LENGTH_DEFAULT ) ) {
                    node.setDistanceToParent( PhylogenyDataUtil.BRANCH_LENGTH_DEFAULT );
                }
                else {
                    node.setDistanceToParent( ( c.getDistanceToParent() >= 0.0 ? c.getDistanceToParent() : 0.0 )
                            + ( node.getDistanceToParent() >= 0.0 ? node.getDistanceToParent() : 0.0 ) );
                }
                if ( c.getBranchDataDirectly() != null ) {
                    node.setBranchData( ( BranchData ) c.getBranchDataDirectly().copy() );
                }
                for( int i = 0; i < b.getNumberOfDescendants(); ++i ) {
                    if ( b.getChildNode( i ) == c ) {
                        b.setChildNodeOnly( i, node );
                        break;
                    }
                }
            }
            else {
                c.setParent( b );
                c.removeChildNode( b.getChildNodeIndex( c ) );
            }
            setRoot( new_root );
        }
    }

[invitef1f76460]

Ah ah ah ! J'ai réussi !!! Dieu existe
Donc en gros j'avais bien adapté la fonction, mais il manquait un return du nouvel arbre que la fonction ne faisait pas ...
Bon y'a que moi qui contente mais c'est le principal hey hey ^^

[invite068a575a]

Eh bien bravo, je pense que tu as mis Dieu comme outgroup? Il y a pas mal d'algorithmique dans cette publi explicitement consacrée au dessin et remaniement d'arbres.

Francis

[JPL]

Eh bien bravo, je pense que tu as mis Dieu comme outgroup?

Non, juste les Bogdanov