2 // FORESTER -- software libraries and applications
3 // for evolutionary biology research and applications.
5 // Copyright (C) 2008-2009 Christian M. Zmasek
6 // Copyright (C) 2008-2009 Burnham Institute for Medical Research
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.
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.
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
23 // Contact: phylosoft @ gmail . com
24 // WWW: www.phylosoft.org/forester
26 package org.forester.tools;
28 import java.util.ArrayList;
29 import java.util.HashMap;
30 import java.util.List;
32 import java.util.NoSuchElementException;
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;
41 * A simple class containing a static method to evaluate the topology of a given
42 * phylogeny with a list of resampled phylogenies.
45 * @author Christian M Zmasek
47 public final class SupportCount {
49 private SupportCount() {
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 );
63 final String child0_name = phylogeny.getFirstExternalNode().getName();
64 phylogeny.reRoot( phylogeny.getNode( child0_name ) );
65 evaluator_phylogeny.reRoot( evaluator_phylogeny.getNode( child0_name ) );
67 final Map<Integer, ArrayList<String>> phylogeny_external_names_per_node = SupportCount
68 .extractExternalNamesPerNode( phylogeny );
69 return ( SupportCount.compare( phylogeny,
71 phylogeny_external_names_per_node,
72 update_support_in_phylogeny,
78 * Precondition: phylogeny and evaluator_phylogeny have to be rooted in the
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.
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
98 private static double compare( final Phylogeny phylogeny,
99 final Phylogeny evaluator_phylogeny,
100 final Map<Integer, 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;
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
113 final List<String> c1 = new ArrayList<String>();
114 for( final Object element : evaluator_phylogeny_it.next().getAllExternalDescendants() ) {
115 c1.add( ( ( PhylogenyNode ) element ).getName() );
117 for( final Integer 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 ) {
123 if ( update_support_in_phylogeny ) {
124 final PhylogenyNode node = phylogeny.getNode( id.intValue() );
125 double d = PhylogenyMethods.getConfidenceValue( node );
132 support_values.put( node, new Double( d ) );
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();
145 PhylogenyMethods.setBootstrapConfidence( node, b );
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 );
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.
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
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();
182 final String child0_name = phylogeny.getFirstExternalNode().getName();
183 phylogeny.reRoot( phylogeny.getNode( child0_name ) );
184 final Map<Integer, ArrayList<String>> phylogeny_external_names_per_node = SupportCount
185 .extractExternalNamesPerNode( phylogeny );
187 System.out.println();
188 System.out.println( "evaluator phylogeny #: similarity score (max is 1.0)" );
189 System.out.println( "----------------------------------------------------" );
190 System.out.println();
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(),
202 DESCENDANT_SORT_PRIORITY.TAXONOMY ); // This is for
208 final double s = SupportCount.compare( phylogeny,
209 evaluator_phylogenies[ i ],
210 phylogeny_external_names_per_node,
212 similarity_threshold );
213 if ( ( similarity_threshold < 0.0 ) || ( s >= similarity_threshold ) ) {
214 PhylogenyMethods.orderAppearance( unstripped_evaluator_phylogeny.getRoot(),
217 DESCENDANT_SORT_PRIORITY.TAXONOMY );
218 evaluator_phylogenies_above_threshold.add( unstripped_evaluator_phylogeny );
221 if ( similarity_threshold < 0.0 ) {
222 System.out.println( i + ": " + s );
224 else if ( s >= similarity_threshold ) {
225 System.out.println( i + ": " + s + " <====" );
228 System.out.println( i + ": " + s );
233 System.out.println( "----------------------------------------------------" );
234 System.out.println();
236 return evaluator_phylogenies_above_threshold;
239 private static Map<Integer, ArrayList<String>> extractExternalNamesPerNode( final Phylogeny phylogeny )
240 throws NoSuchElementException {
241 final HashMap<Integer, ArrayList<String>> phylogeny_external_names_per_node = new HashMap<Integer, ArrayList<String>>();
242 for( final PhylogenyNodeIterator it = phylogeny.iteratorPostorder(); it.hasNext(); ) {
243 final PhylogenyNode n = it.next();
244 final List<PhylogenyNode> l = n.getAllExternalDescendants();
245 final ArrayList<String> c = new ArrayList<String>();
246 phylogeny_external_names_per_node.put( new Integer( n.getId() ), c );
247 for( final PhylogenyNode phylogenyNode : l ) {
248 c.add( phylogenyNode.getName() );
251 return phylogeny_external_names_per_node;
254 private static void strip( final String[] to_keep, final Phylogeny to_be_stripped ) {
255 PhylogenyMethods.deleteExternalNodesPositiveSelection( to_keep, to_be_stripped );