forester/java/src/org/forester/tools/SupportCount.java

   1 // $Id:
   2 // FORESTER -- software libraries and applications
   3 // for evolutionary biology research and applications.
   4 //
   5 // Copyright (C) 2008-2009 Christian M. Zmasek
   6 // Copyright (C) 2008-2009 Burnham Institute for Medical Research
   7 // All rights reserved
   8 //
   9 // This library is free software; you can redistribute it and/or
  10 // modify it under the terms of the GNU Lesser General Public
  11 // License as published by the Free Software Foundation; either
  12 // version 2.1 of the License, or (at your option) any later version.
  13 //
  14 // This library is distributed in the hope that it will be useful,
  15 // but WITHOUT ANY WARRANTY; without even the implied warranty of
  16 // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
  17 // Lesser General Public License for more details.
  18 //
  19 // You should have received a copy of the GNU Lesser General Public
  20 // License along with this library; if not, write to the Free Software
  21 // Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA
  22 //
  23 // Contact: phylosoft @ gmail . com
  24 // WWW: www.phylosoft.org/forester
  25
  26 package org.forester.tools;
  27
  28 import java.util.ArrayList;
  29 import java.util.HashMap;
  30 import java.util.List;
  31 import java.util.Map;
  32 import java.util.NoSuchElementException;
  33
  34 import org.forester.phylogeny.Phylogeny;
  35 import org.forester.phylogeny.PhylogenyMethods;
  36 import org.forester.phylogeny.PhylogenyNode;
  37 import org.forester.phylogeny.iterators.PhylogenyNodeIterator;
  38
  39 /*
  40  * A simple class containing a static method to evaluate the topology of a given
  41  * phylogeny with a list of resampled phylogenies.
  42  *
  43  *
  44  * @author Christian M Zmasek
  45  */
  46 public final class SupportCount {
  47
  48     private SupportCount() {
  49     }
  50
  51     public static double compare( final Phylogeny phylogeny,
  52                                   final Phylogeny evaluator_phylogeny,
  53                                   final boolean strip_evaluator_phylogeny,
  54                                   final boolean update_support_in_phylogeny,
  55                                   final boolean re_root ) {
  56         String[] seq_names_to_keep = null;
  57         if ( strip_evaluator_phylogeny ) {
  58             seq_names_to_keep = phylogeny.getAllExternalNodeNames();
  59             SupportCount.strip( seq_names_to_keep, evaluator_phylogeny );
  60         }
  61         if ( re_root ) {
  62             final String child0_name = phylogeny.getFirstExternalNode().getName();
  63             phylogeny.reRoot( phylogeny.getNode( child0_name ) );
  64             evaluator_phylogeny.reRoot( evaluator_phylogeny.getNode( child0_name ) );
  65         }
  66         final Map<Integer, ArrayList<String>> phylogeny_external_names_per_node = SupportCount
  67                 .extractExternalNamesPerNode( phylogeny );
  68         return ( SupportCount.compare( phylogeny,
  69                                        evaluator_phylogeny,
  70                                        phylogeny_external_names_per_node,
  71                                        update_support_in_phylogeny,
  72                                        -1 ) );
  73     }
  74
  75     /**
  76      *
  77      * Precondition: phylogeny and evaluator_phylogeny have to be rooted in the
  78      * same manner.
  79      *
  80      * Returns a measure of the similarity ("average bootstrap similarity")
  81      * between the topologies of phylogeny and evaluator_phylogeny: (sum of
  82      * branches which divide phylogeny in a manner consitent with
  83      * evaluator_phylogeny)/sum of branches in phylogeny. Therefore, this
  84      * measure is 1.0 for indentical topologies and 0.0 for completely
  85      * incompatible topologies.
  86      *
  87      *
  88      * @param phylogeny
  89      * @param evaluator_phylogeny
  90      * @param external_names_per_node
  91      * @param update_support_in_phylogeny
  92      *            set to true to update support values in phylogeny, otherwise,
  93      *            just calculation of the "average bootstrap similarity"
  94      * @return a measure of the similarity ("average bootstrap similarity")
  95      *         between phylogeny and evaluator_phylogeny
  96      */
  97     private static double compare( final Phylogeny phylogeny,
  98                                    final Phylogeny evaluator_phylogeny,
  99                                    final Map<Integer, ArrayList<String>> phylogeny_external_names_per_node,
 100                                    final boolean update_support_in_phylogeny,
 101                                    final double similarity_threshold ) {
 102         int matching_branches = 0;
 103         int phylogeny_total_internal_branches = 0;
 104         for( final PhylogenyNodeIterator it = phylogeny.iteratorPostorder(); it.hasNext(); ) {
 105             if ( !it.next().isExternal() ) {
 106                 ++phylogeny_total_internal_branches;
 107             }
 108         }
 109         final Map<PhylogenyNode, Double> support_values = new HashMap<PhylogenyNode, Double>();
 110         E: for( final PhylogenyNodeIterator evaluator_phylogeny_it = evaluator_phylogeny.iteratorPostorder(); evaluator_phylogeny_it
 111                 .hasNext(); ) {
 112             final List<String> c1 = new ArrayList<String>();
 113             for( final Object element : evaluator_phylogeny_it.next().getAllExternalDescendants() ) {
 114                 c1.add( ( ( PhylogenyNode ) element ).getName() );
 115             }
 116             for( final Integer id : phylogeny_external_names_per_node.keySet() ) {
 117                 final List<String> c2 = phylogeny_external_names_per_node.get( id );
 118                 if ( ( c2.size() == c1.size() ) && c2.containsAll( c1 ) ) {
 119                     if ( c2.size() > 1 ) {
 120                         matching_branches++;
 121                     }
 122                     if ( update_support_in_phylogeny ) {
 123                         final PhylogenyNode node = phylogeny.getNode( id.intValue() );
 124                         double d = PhylogenyMethods.getConfidenceValue( node );
 125                         if ( d < 1.0 ) {
 126                             d = 1.0;
 127                         }
 128                         else {
 129                             ++d;
 130                         }
 131                         support_values.put( node, new Double( d ) );
 132                     }
 133                     continue E;
 134                 }
 135             }
 136         }
 137         final double similarity = ( double ) matching_branches / phylogeny_total_internal_branches;
 138         if ( ( similarity_threshold < 0.0 ) || ( similarity >= similarity_threshold ) ) {
 139             for( final PhylogenyNode node : support_values.keySet() ) {
 140                 double b = support_values.get( node ).doubleValue();
 141                 if ( b < 0 ) {
 142                     b = 0.0;
 143                 }
 144                 PhylogenyMethods.setBootstrapConfidence( node, b );
 145             }
 146         }
 147         return similarity;
 148     }
 149
 150     public static void count( final Phylogeny phylogeny,
 151                               final Phylogeny[] evaluator_phylogenies,
 152                               final boolean strip_evaluator_phylogenies,
 153                               final boolean verbose ) {
 154         SupportCount.count( phylogeny, evaluator_phylogenies, strip_evaluator_phylogenies, -1, verbose );
 155     }
 156
 157     /**
 158      * This counts the support of topology phylogeny by the topologies in
 159      * phylogenies. If phylogenies contains topogies with names not present in
 160      * phylogeny, strip_phylogenies must be set to true. phylogeny must not
 161      * contain names not found in all phylogenies.
 162      *
 163      * @param phylogeny
 164      *            the topology to be evaluated
 165      * @param evaluator_phylogenies
 166      *            the topologies used for evaluation
 167      * @param strip_evaluator_phylogenies
 168      *            set to true if phylogenies contains topologies with names not
 169      *            present in phylogeny
 170      */
 171     public static List<Phylogeny> count( final Phylogeny phylogeny,
 172                                          final Phylogeny[] evaluator_phylogenies,
 173                                          final boolean strip_evaluator_phylogenies,
 174                                          final double similarity_threshold,
 175                                          final boolean verbose ) {
 176         String[] seq_names_to_keep = null;
 177         final List<Phylogeny> evaluator_phylogenies_above_threshold = new ArrayList<Phylogeny>();
 178         if ( strip_evaluator_phylogenies ) {
 179             seq_names_to_keep = phylogeny.getAllExternalNodeNames();
 180         }
 181         final String child0_name = phylogeny.getFirstExternalNode().getName();
 182         phylogeny.reRoot( phylogeny.getNode( child0_name ) );
 183         final Map<Integer, ArrayList<String>> phylogeny_external_names_per_node = SupportCount
 184                 .extractExternalNamesPerNode( phylogeny );
 185         if ( verbose ) {
 186             System.out.println();
 187             System.out.println( "evaluator phylogeny #: similarity score (max is 1.0)" );
 188             System.out.println( "----------------------------------------------------" );
 189             System.out.println();
 190         }
 191         for( int i = 0; i < evaluator_phylogenies.length; ++i ) {
 192             final Phylogeny evaluator_phylogeny = evaluator_phylogenies[ i ];
 193             evaluator_phylogeny.reRoot( evaluator_phylogeny.getNode( child0_name ) );
 194             Phylogeny unstripped_evaluator_phylogeny = evaluator_phylogeny;
 195             if ( strip_evaluator_phylogenies ) {
 196                 unstripped_evaluator_phylogeny = evaluator_phylogeny.copy();
 197                 SupportCount.strip( seq_names_to_keep, evaluator_phylogeny );
 198                 evaluator_phylogeny.orderAppearance( true ); // This is for
 199                 // easer
 200                 // comparison if
 201                 // phylos are saved
 202                 // to file.
 203             }
 204             final double s = SupportCount.compare( phylogeny,
 205                                                    evaluator_phylogenies[ i ],
 206                                                    phylogeny_external_names_per_node,
 207                                                    true,
 208                                                    similarity_threshold );
 209             if ( ( similarity_threshold < 0.0 ) || ( s >= similarity_threshold ) ) {
 210                 unstripped_evaluator_phylogeny.orderAppearance( true );
 211                 evaluator_phylogenies_above_threshold.add( unstripped_evaluator_phylogeny );
 212             }
 213             if ( verbose ) {
 214                 if ( similarity_threshold < 0.0 ) {
 215                     System.out.println( i + ": " + s );
 216                 }
 217                 else if ( s >= similarity_threshold ) {
 218                     System.out.println( i + ": " + s + " <====" );
 219                 }
 220                 else {
 221                     System.out.println( i + ": " + s );
 222                 }
 223             }
 224         }
 225         if ( verbose ) {
 226             System.out.println( "----------------------------------------------------" );
 227             System.out.println();
 228         }
 229         return evaluator_phylogenies_above_threshold;
 230     }
 231
 232     private static Map<Integer, ArrayList<String>> extractExternalNamesPerNode( final Phylogeny phylogeny )
 233             throws NoSuchElementException {
 234         final HashMap<Integer, ArrayList<String>> phylogeny_external_names_per_node = new HashMap<Integer, ArrayList<String>>();
 235         for( final PhylogenyNodeIterator it = phylogeny.iteratorPostorder(); it.hasNext(); ) {
 236             final PhylogenyNode n = it.next();
 237             final List<PhylogenyNode> l = n.getAllExternalDescendants();
 238             final ArrayList<String> c = new ArrayList<String>();
 239             phylogeny_external_names_per_node.put( new Integer( n.getId() ), c );
 240             for( final PhylogenyNode phylogenyNode : l ) {
 241                 c.add( phylogenyNode.getName() );
 242             }
 243         }
 244         return phylogeny_external_names_per_node;
 245     }
 246
 247     private static void strip( final String[] to_keep, final Phylogeny to_be_stripped ) {
 248         PhylogenyMethods.deleteExternalNodesPositiveSelection( to_keep, to_be_stripped );
 249     }
 250 }