2 // FORESTER -- software libraries and applications
3 // for evolutionary biology research and applications.
5 // Copyright (C) 2017 Christian M. Zmasek
6 // Copyright (C) 2017 J. Craig Venter Institute
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: phyloxml @ gmail . com
24 // WWW: https://sites.google.com/site/cmzmasek/home/software/forester
25 // --------------------
27 // * Multiple "hits" with different "M" values
28 // * More tests (including multiple children per node), especially on edge cases
29 // * Utilize relevant support values for warnings
31 package org.forester.clade_analysis;
33 import java.util.ArrayList;
34 import java.util.Collections;
35 import java.util.List;
37 import org.forester.phylogeny.Phylogeny;
38 import org.forester.phylogeny.PhylogenyNode;
39 import org.forester.phylogeny.data.Confidence;
40 import org.forester.util.ForesterUtil;
42 public final class Analysis2 {
44 public static Result2 execute( final Phylogeny p, final String query, final String separator ) {
45 final PhylogenyNode qnode = p.getNode( query );
46 if ( qnode.isRoot() ) {
47 throw new IllegalStateException( "Unexpected error: Query " + query
48 + " is root. This should have never happened" );
50 if ( qnode.getParent().isRoot() ) {
51 throw new IllegalStateException( "Unexpected error: Parent of query " + query
52 + " is root. This should have never happened" );
54 PhylogenyNode qnode_p = qnode.getParent();
55 PhylogenyNode qnode_pp = qnode.getParent().getParent();
56 while ( qnode_p.getNumberOfDescendants() == 1 ) {
57 qnode_p = qnode_p.getParent();
59 while ( qnode_pp.getNumberOfDescendants() == 1 ) {
60 qnode_pp = qnode_pp.getParent();
62 final List<PhylogenyNode> qnode_ext_nodes = qnode_pp.getAllExternalDescendants();
63 final int lec_ext_nodes = qnode_ext_nodes.size() - 1;
64 final int p_ext_nodes = p.getNumberOfExternalNodes() - 1;
65 final List<String> qnode_ext_nodes_names = new ArrayList<>();
66 for( final PhylogenyNode qnode_ext_node : qnode_ext_nodes ) {
67 String name = qnode_ext_node.getName();
68 if ( ForesterUtil.isEmptyTrimmed( name ) ) {
69 throw new IllegalArgumentException( "external node(s) with empty names found" );
72 if ( !name.equals( query ) ) {
73 qnode_ext_nodes_names.add( name );
76 final String greatest_common_prefix = ForesterUtil.greatestCommonPrefix( qnode_ext_nodes_names, separator );
77 final Result2 res = new Result2();
78 if ( greatest_common_prefix.length() < 1 ) {
79 res.addWarning( "No greatest common prefix" );
80 //res.setGreatestCommonPrefix( "" );
83 // res.setGreatestCommonPrefix( greatest_common_prefix );
84 // res.addGreatestCommonPrefix( prefix, confidence, separator ); //TODO
86 if ( qnode_pp.isRoot() ) {
87 res.addWarning( "Least Encompassing Clade is entire tree" );
89 res.setLeastEncompassingCladeSize( lec_ext_nodes );
90 res.setTreeSize( p_ext_nodes );
92 final String conf = obtainConfidence( qnode_pp );
94 res.setGreatestCommonCladeSubtreeConfidence(conf);
97 final String greatest_common_prefix_up[] = analyzeSiblings( qnode_p, qnode_pp, separator );
98 res.setGreatestCommonPrefixUp( greatest_common_prefix_up[ 0 ] );
99 if ( greatest_common_prefix_up[ 1 ] != null ) {
100 res.setGreatestCommonCladeUpSubtreeConfidence( greatest_common_prefix_up[ 1 ] );
102 final String greatest_common_prefix_down[] = analyzeSiblings( qnode, qnode_p, separator );
103 res.setGreatestCommonPrefixDown( greatest_common_prefix_down[ 0 ] );
104 if ( greatest_common_prefix_down[ 1 ] != null ) {
105 res.setGreatestCommonCladeDownSubtreeConfidence( greatest_common_prefix_down[ 1 ] );
112 private final static String[] analyzeSiblings( final PhylogenyNode child,
113 final PhylogenyNode parent,
114 final String separator ) {
115 final int child_index = child.getChildNodeIndex();
116 final List<String> ext_nodes_names = new ArrayList<>();
117 final List<PhylogenyNode> descs = parent.getDescendants();
119 for( int i = 0; i < descs.size(); ++i ) {
120 if ( i != child_index ) {
121 final PhylogenyNode d = descs.get( i );
122 for( final PhylogenyNode n : d.getAllExternalDescendants() ) {
123 final String name = n.getName();
124 if ( ForesterUtil.isEmptyTrimmed( name ) ) {
125 throw new IllegalArgumentException( "external node(s) with empty names found" );
127 ext_nodes_names.add( name.trim() );
129 if ( descs.size() == 2 ) {
130 conf = obtainConfidence( d );
134 final String greatest_common_prefix = ForesterUtil.greatestCommonPrefix( ext_nodes_names, separator );
135 return new String[] { greatest_common_prefix, conf };
138 private final static String obtainConfidence( final PhylogenyNode n ) {
139 if ( n.getBranchData().getConfidences() != null && n.getBranchData().getConfidences().size() > 0 ) {
140 final List<Confidence> confidences = n.getBranchData().getConfidences();
141 boolean not_first = false;
142 Collections.sort( confidences );
143 final StringBuilder sb = new StringBuilder();
144 for( final Confidence confidence : confidences ) {
145 final double value = confidence.getValue();
146 if ( value != Confidence.CONFIDENCE_DEFAULT_VALUE ) {
153 sb.append( ( ForesterUtil.isEmpty( confidence.getType() ) ? "confidence: "
154 : confidence.getType() + ": " ) + value );
157 return sb.toString();