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: https://sites.google.com/site/cmzmasek/home/software/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.PhylogenyMethods.DESCENDANT_SORT_PRIORITY;
  37 import org.forester.phylogeny.PhylogenyNode;
  38 import org.forester.phylogeny.iterators.PhylogenyNodeIterator;
  39
  40 /*
  41  * A simple class containing a static method to evaluate the topology of a given
  42  * phylogeny with a list of resampled phylogenies.
  43  *
  44  *
  45  * @author Christian M Zmasek
  46  */
  47 public final class SupportCount {
  48
  49     private SupportCount() {
  50     }
  51
  52     public static double compare( final Phylogeny phylogeny,
  53                                   final Phylogeny evaluator_phylogeny,
  54                                   final boolean strip_evaluator_phylogeny,
  55                                   final boolean update_support_in_phylogeny,
  56                                   final boolean re_root ) {
  57         String[] seq_names_to_keep = null;
  58         if ( strip_evaluator_phylogeny ) {
  59             seq_names_to_keep = phylogeny.getAllExternalNodeNames();
  60             SupportCount.strip( seq_names_to_keep, evaluator_phylogeny );
  61         }
  62         if ( re_root ) {
  63             final String child0_name = phylogeny.getFirstExternalNode().getName();
  64             phylogeny.reRoot( phylogeny.getNode( child0_name ) );
  65             evaluator_phylogeny.reRoot( evaluator_phylogeny.getNode( child0_name ) );
  66         }
  67         final Map<Long, ArrayList<String>> phylogeny_external_names_per_node = SupportCount
  68                 .extractExternalNamesPerNode( phylogeny );
  69         return ( SupportCount.compare( phylogeny,
  70                                        evaluator_phylogeny,
  71                                        phylogeny_external_names_per_node,
  72                                        update_support_in_phylogeny,
  73                                        -1 ) );
  74     }
  75
  76     /**
  77      *
  78      * Precondition: phylogeny and evaluator_phylogeny have to be rooted in the
  79      * same manner.
  80      *
  81      * Returns a measure of the similarity ("average bootstrap similarity")
  82      * between the topologies of phylogeny and evaluator_phylogeny: (sum of
  83      * branches which divide phylogeny in a manner consitent with
  84      * evaluator_phylogeny)/sum of branches in phylogeny. Therefore, this
  85      * measure is 1.0 for indentical topologies and 0.0 for completely
  86      * incompatible topologies.
  87      *
  88      *
  89      * @param phylogeny
  90      * @param evaluator_phylogeny
  91      * @param external_names_per_node
  92      * @param update_support_in_phylogeny
  93      *            set to true to update support values in phylogeny, otherwise,
  94      *            just calculation of the "average bootstrap similarity"
  95      * @return a measure of the similarity ("average bootstrap similarity")
  96      *         between phylogeny and evaluator_phylogeny
  97      */
  98     private static double compare( final Phylogeny phylogeny,
  99                                    final Phylogeny evaluator_phylogeny,
 100                                    final Map<Long, ArrayList<String>> phylogeny_external_names_per_node,
 101                                    final boolean update_support_in_phylogeny,
 102                                    final double similarity_threshold ) {
 103         int matching_branches = 0;
 104         int phylogeny_total_internal_branches = 0;
 105         for( final PhylogenyNodeIterator it = phylogeny.iteratorPostorder(); it.hasNext(); ) {
 106             if ( !it.next().isExternal() ) {
 107                 ++phylogeny_total_internal_branches;
 108             }
 109         }
 110         final Map<PhylogenyNode, Double> support_values = new HashMap<PhylogenyNode, Double>();
 111         E: for( final PhylogenyNodeIterator evaluator_phylogeny_it = evaluator_phylogeny.iteratorPostorder(); evaluator_phylogeny_it
 112                 .hasNext(); ) {
 113             final List<String> c1 = new ArrayList<String>();
 114             for( final Object element : evaluator_phylogeny_it.next().getAllExternalDescendants() ) {
 115                 c1.add( ( ( PhylogenyNode ) element ).getName() );
 116             }
 117             for( final Long id : phylogeny_external_names_per_node.keySet() ) {
 118                 final List<String> c2 = phylogeny_external_names_per_node.get( id );
 119                 if ( ( c2.size() == c1.size() ) && c2.containsAll( c1 ) ) {
 120                     if ( c2.size() > 1 ) {
 121                         matching_branches++;
 122                     }
 123                     if ( update_support_in_phylogeny ) {
 124                         final PhylogenyNode node = phylogeny.getNode( id.intValue() );
 125                         double d = PhylogenyMethods.getConfidenceValue( node );
 126                         if ( d < 1.0 ) {
 127                             d = 1.0;
 128                         }
 129                         else {
 130                             ++d;
 131                         }
 132                         support_values.put( node, new Double( d ) );
 133                     }
 134                     continue E;
 135                 }
 136             }
 137         }
 138         final double similarity = ( double ) matching_branches / phylogeny_total_internal_branches;
 139         if ( ( similarity_threshold < 0.0 ) || ( similarity >= similarity_threshold ) ) {
 140             for( final PhylogenyNode node : support_values.keySet() ) {
 141                 double b = support_values.get( node ).doubleValue();
 142                 if ( b < 0 ) {
 143                     b = 0.0;
 144                 }
 145                 PhylogenyMethods.setBootstrapConfidence( node, b );
 146             }
 147         }
 148         return similarity;
 149     }
 150
 151     public static void count( final Phylogeny phylogeny,
 152                               final Phylogeny[] evaluator_phylogenies,
 153                               final boolean strip_evaluator_phylogenies,
 154                               final boolean verbose ) {
 155         SupportCount.count( phylogeny, evaluator_phylogenies, strip_evaluator_phylogenies, -1, verbose );
 156     }
 157
 158     /**
 159      * This counts the support of topology phylogeny by the topologies in
 160      * phylogenies. If phylogenies contains topogies with names not present in
 161      * phylogeny, strip_phylogenies must be set to true. phylogeny must not
 162      * contain names not found in all phylogenies.
 163      *
 164      * @param phylogeny
 165      *            the topology to be evaluated
 166      * @param evaluator_phylogenies
 167      *            the topologies used for evaluation
 168      * @param strip_evaluator_phylogenies
 169      *            set to true if phylogenies contains topologies with names not
 170      *            present in phylogeny
 171      */
 172     public static List<Phylogeny> count( final Phylogeny phylogeny,
 173                                          final Phylogeny[] evaluator_phylogenies,
 174                                          final boolean strip_evaluator_phylogenies,
 175                                          final double similarity_threshold,
 176                                          final boolean verbose ) {
 177         String[] seq_names_to_keep = null;
 178         final List<Phylogeny> evaluator_phylogenies_above_threshold = new ArrayList<Phylogeny>();
 179         if ( strip_evaluator_phylogenies ) {
 180             seq_names_to_keep = phylogeny.getAllExternalNodeNames();
 181         }
 182         final String child0_name = phylogeny.getFirstExternalNode().getName();
 183         phylogeny.reRoot( phylogeny.getNode( child0_name ) );
 184         final Map<Long, ArrayList<String>> phylogeny_external_names_per_node = SupportCount
 185                 .extractExternalNamesPerNode( phylogeny );
 186         if ( verbose ) {
 187             System.out.println();
 188             System.out.println( "evaluator phylogeny #: similarity score (max is 1.0)" );
 189             System.out.println( "----------------------------------------------------" );
 190             System.out.println();
 191         }
 192         for( int i = 0; i < evaluator_phylogenies.length; ++i ) {
 193             final Phylogeny evaluator_phylogeny = evaluator_phylogenies[ i ];
 194             evaluator_phylogeny.reRoot( evaluator_phylogeny.getNode( child0_name ) );
 195             Phylogeny unstripped_evaluator_phylogeny = evaluator_phylogeny;
 196             if ( strip_evaluator_phylogenies ) {
 197                 unstripped_evaluator_phylogeny = evaluator_phylogeny.copy();
 198                 SupportCount.strip( seq_names_to_keep, evaluator_phylogeny );
 199                 PhylogenyMethods.orderAppearance( evaluator_phylogeny.getRoot(),
 200                                                   true,
 201                                                   true,
 202                                                   DESCENDANT_SORT_PRIORITY.TAXONOMY ); // This is for
 203                 // easer
 204                 // comparison if
 205                 // phylos are saved
 206                 // to file.
 207                 evaluator_phylogeny.externalNodesHaveChanged();
 208                 evaluator_phylogeny.clearHashIdToNodeMap();
 209                 evaluator_phylogeny.recalculateNumberOfExternalDescendants( true );
 210             }
 211             final double s = SupportCount.compare( phylogeny,
 212                                                    evaluator_phylogenies[ i ],
 213                                                    phylogeny_external_names_per_node,
 214                                                    true,
 215                                                    similarity_threshold );
 216             if ( ( similarity_threshold < 0.0 ) || ( s >= similarity_threshold ) ) {
 217                 PhylogenyMethods.orderAppearance( unstripped_evaluator_phylogeny.getRoot(),
 218                                                   true,
 219                                                   true,
 220                                                   DESCENDANT_SORT_PRIORITY.TAXONOMY );
 221                 evaluator_phylogenies_above_threshold.add( unstripped_evaluator_phylogeny );
 222             }
 223             if ( verbose ) {
 224                 if ( similarity_threshold < 0.0 ) {
 225                     System.out.println( i + ": " + s );
 226                 }
 227                 else if ( s >= similarity_threshold ) {
 228                     System.out.println( i + ": " + s + " <====" );
 229                 }
 230                 else {
 231                     System.out.println( i + ": " + s );
 232                 }
 233             }
 234         }
 235         if ( verbose ) {
 236             System.out.println( "----------------------------------------------------" );
 237             System.out.println();
 238         }
 239         return evaluator_phylogenies_above_threshold;
 240     }
 241
 242     private static Map<Long, ArrayList<String>> extractExternalNamesPerNode( final Phylogeny phylogeny )
 243             throws NoSuchElementException {
 244         final HashMap<Long, ArrayList<String>> phylogeny_external_names_per_node = new HashMap<Long, ArrayList<String>>();
 245         for( final PhylogenyNodeIterator it = phylogeny.iteratorPostorder(); it.hasNext(); ) {
 246             final PhylogenyNode n = it.next();
 247             final List<PhylogenyNode> l = n.getAllExternalDescendants();
 248             final ArrayList<String> c = new ArrayList<String>();
 249             phylogeny_external_names_per_node.put( new Long( n.getId() ), c );
 250             for( final PhylogenyNode phylogenyNode : l ) {
 251                 c.add( phylogenyNode.getName() );
 252             }
 253         }
 254         return phylogeny_external_names_per_node;
 255     }
 256
 257     private static void strip( final String[] to_keep, final Phylogeny to_be_stripped ) {
 258         PhylogenyMethods.deleteExternalNodesPositiveSelection( to_keep, to_be_stripped );
 259     }
 260 }