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.PhylogenyNode;
37 import org.forester.phylogeny.iterators.PhylogenyNodeIterator;
40 * A simple class containing a static method to evaluate the topology of a given
41 * phylogeny with a list of resampled phylogenies.
44 * @author Christian M Zmasek
46 public final class SupportCount {
48 private SupportCount() {
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 );
62 final String child0_name = phylogeny.getFirstExternalNode().getName();
63 phylogeny.reRoot( phylogeny.getNode( child0_name ) );
64 evaluator_phylogeny.reRoot( evaluator_phylogeny.getNode( child0_name ) );
66 final Map<Integer, ArrayList<String>> phylogeny_external_names_per_node = SupportCount
67 .extractExternalNamesPerNode( phylogeny );
68 return ( SupportCount.compare( phylogeny,
70 phylogeny_external_names_per_node,
71 update_support_in_phylogeny,
77 * Precondition: phylogeny and evaluator_phylogeny have to be rooted in the
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.
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
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;
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
112 final List<String> c1 = new ArrayList<String>();
113 for( final Object element : evaluator_phylogeny_it.next().getAllExternalDescendants() ) {
114 c1.add( ( ( PhylogenyNode ) element ).getName() );
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 ) {
122 if ( update_support_in_phylogeny ) {
123 final PhylogenyNode node = phylogeny.getNode( id.intValue() );
124 double d = PhylogenyMethods.getConfidenceValue( node );
131 support_values.put( node, new Double( d ) );
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();
144 PhylogenyMethods.setBootstrapConfidence( node, b );
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 );
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.
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
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();
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 );
186 System.out.println();
187 System.out.println( "evaluator phylogeny #: similarity score (max is 1.0)" );
188 System.out.println( "----------------------------------------------------" );
189 System.out.println();
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
204 final double s = SupportCount.compare( phylogeny,
205 evaluator_phylogenies[ i ],
206 phylogeny_external_names_per_node,
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 );
214 if ( similarity_threshold < 0.0 ) {
215 System.out.println( i + ": " + s );
217 else if ( s >= similarity_threshold ) {
218 System.out.println( i + ": " + s + " <====" );
221 System.out.println( i + ": " + s );
226 System.out.println( "----------------------------------------------------" );
227 System.out.println();
229 return evaluator_phylogenies_above_threshold;
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() );
244 return phylogeny_external_names_per_node;
247 private static void strip( final String[] to_keep, final Phylogeny to_be_stripped ) {
248 PhylogenyMethods.deleteExternalNodesPositiveSelection( to_keep, to_be_stripped );