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;
36 import java.util.SortedMap;
37 import java.util.regex.Matcher;
38 import java.util.regex.Pattern;
40 import org.forester.phylogeny.Phylogeny;
41 import org.forester.phylogeny.PhylogenyNode;
42 import org.forester.phylogeny.data.Confidence;
43 import org.forester.phylogeny.iterators.PhylogenyNodeIterator;
44 import org.forester.util.ForesterUtil;
45 import org.forester.util.UserException;
47 public final class AnalysisMulti {
49 private final static String UNKNOWN = "?";
50 public final static double DEFAULT_CUTOFF_FOR_SPECIFICS = 0.5;
51 public final static String DEFAULT_SEPARATOR = ".";
52 public final static Pattern DEFAULT_QUERY_PATTERN_FOR_PPLACER_TYPE = Pattern.compile( "_#\\d+_M=(.+)" );
54 public static ResultMulti execute( final Phylogeny p ) throws UserException {
55 return execute( p, DEFAULT_QUERY_PATTERN_FOR_PPLACER_TYPE, DEFAULT_SEPARATOR, DEFAULT_CUTOFF_FOR_SPECIFICS );
58 public static ResultMulti execute( final Phylogeny p, final String separator ) throws UserException {
59 return execute( p, DEFAULT_QUERY_PATTERN_FOR_PPLACER_TYPE, separator, DEFAULT_CUTOFF_FOR_SPECIFICS );
62 public static ResultMulti execute( final Phylogeny p, final String separator, final double cutoff_for_specifics )
63 throws UserException {
64 return execute( p, DEFAULT_QUERY_PATTERN_FOR_PPLACER_TYPE, separator, cutoff_for_specifics );
67 public static ResultMulti execute( final Phylogeny p, final double cutoff_for_specifics ) throws UserException {
68 return execute( p, DEFAULT_QUERY_PATTERN_FOR_PPLACER_TYPE, DEFAULT_SEPARATOR, cutoff_for_specifics );
71 public static ResultMulti execute( final Phylogeny p,
73 final String separator,
74 final double cutoff_for_specifics )
75 throws UserException {
76 cleanUpExternalNames( p, separator );
77 final List<PhylogenyNode> qnodes = p.getNodes( query );
78 String query_name_prefix = null;
79 for( final PhylogenyNode n : qnodes ) {
80 final String name = n.getName();
81 final Matcher matcher = query.matcher( name );
82 if ( matcher.find() ) {
83 final String prefix = name.substring( 0, matcher.start() );
84 if ( ForesterUtil.isEmpty( prefix ) ) {
85 throw new UserException( "query nodes with empty label prefix found: \"" + prefix + "\"" );
87 if ( query_name_prefix == null ) {
88 query_name_prefix = prefix;
90 else if ( !query_name_prefix.equals( prefix ) ) {
91 throw new UserException( "query nodes with different label prefixes found: \"" + query_name_prefix
92 + "\" and \"" + prefix + "\"" );
96 final ResultMulti res = new ResultMulti();
97 res.setQueryNamePrefix( query_name_prefix );
98 for( int i = 0; i < qnodes.size(); ++i ) {
99 final PhylogenyNode qnode = qnodes.get( i );
100 if ( qnode.isRoot() ) {
101 throw new UserException( "query " + query + " is root" );
103 if ( qnode.getParent().isRoot() ) {
104 throw new UserException( "parent of query " + query + " is root" );
106 PhylogenyNode qnode_p = qnode.getParent();
107 PhylogenyNode qnode_pp = qnode.getParent().getParent();
108 //This is to deal with internal nodes with 1 descendant.
109 while ( qnode_p.getNumberOfDescendants() == 1 ) {
110 qnode_p = qnode_p.getParent();
112 while ( qnode_pp.getNumberOfDescendants() == 1 ) {
113 qnode_pp = qnode_pp.getParent();
115 final List<String> qnode_ext_nodes_names = new ArrayList<>();
116 for( final PhylogenyNode qnode_ext_node : qnode_pp.getAllExternalDescendants() ) {
117 final String name = qnode_ext_node.getName();
118 final Matcher m = query.matcher( name );
120 qnode_ext_nodes_names.add( name );
123 final String greatest_common_prefix = ForesterUtil.greatestCommonPrefix( qnode_ext_nodes_names, separator );
124 final Matcher matcher = query.matcher( qnode.getName() );
125 String conf_str = null;
126 if ( matcher.find() ) {
127 conf_str = matcher.group( 1 );
130 throw new IllegalStateException( "pattern did not match -- this should have never happened!" );
132 final double conf = Double.parseDouble( conf_str );
133 if ( !ForesterUtil.isEmpty( greatest_common_prefix ) ) {
134 res.addGreatestCommonPrefix( greatest_common_prefix, conf );
137 res.addGreatestCommonPrefix( UNKNOWN, conf );
139 final String greatest_common_prefix_up = analyzeSiblings( qnode_p, qnode_pp, separator, query );
140 if ( !ForesterUtil.isEmpty( greatest_common_prefix_up ) ) {
141 res.addGreatestCommonPrefixUp( greatest_common_prefix_up, conf );
144 res.addGreatestCommonPrefixUp( UNKNOWN, conf );
146 final String greatest_common_prefix_down = analyzeSiblings( qnode, qnode_p, separator, query );
147 if ( !ForesterUtil.isEmpty( greatest_common_prefix_down ) ) {
148 res.addGreatestCommonPrefixDown( greatest_common_prefix_down, conf );
151 res.addGreatestCommonPrefixDown( UNKNOWN, conf );
154 res.analyze( cutoff_for_specifics );
158 private final static void cleanUpExternalNames( final Phylogeny p, final String separator ) throws UserException {
159 final Pattern pattern1 = Pattern.compile( "\\Q" + separator + "\\E" + "\\s+" );
160 final Pattern pattern2 = Pattern.compile( "\\s+" + "\\Q" + separator + "\\E" );
161 final Pattern pattern3 = Pattern.compile( "\\Q" + separator + separator + "\\E" );
162 final PhylogenyNodeIterator it = p.iteratorExternalForward();
163 while ( it.hasNext() ) {
164 final PhylogenyNode node = it.next();
165 final String name = node.getName().trim();
166 if ( ForesterUtil.isEmpty( name ) ) {
167 throw new UserException( "external node(s) with empty annotation found" );
169 if ( name.endsWith( separator ) ) {
170 throw new UserException( "illegally formatted annotation found: annotations cannot end with separator: "
173 if ( name.startsWith( separator ) ) {
174 throw new UserException( "illegally formatted annotation found: annotations cannot start with separator: "
177 if ( pattern1.matcher( name ).find() ) {
178 throw new UserException( "illegally formatted annotation found: separator followed by whitespace: "
181 if ( pattern2.matcher( name ).find() ) {
182 throw new UserException( "illegally formatted annotation found: whitespace followed by separator: "
185 if ( pattern3.matcher( name ).find() ) {
186 throw new UserException( "illegally formatted annotation found: empty annotation level: " + name );
188 node.setName( name.replaceAll( "\\s+", " " ) );
192 private final static String analyzeSiblings( final PhylogenyNode child,
193 final PhylogenyNode parent,
194 final String separator,
195 final Pattern query ) {
196 final int child_index = child.getChildNodeIndex();
197 final List<String> ext_nodes_names = new ArrayList<>();
198 final List<PhylogenyNode> descs = parent.getDescendants();
199 for( int i = 0; i < descs.size(); ++i ) {
200 if ( i != child_index ) {
201 final PhylogenyNode d = descs.get( i );
202 for( final PhylogenyNode n : d.getAllExternalDescendants() ) {
203 final String name = n.getName();
204 final Matcher m = query.matcher( name );
206 ext_nodes_names.add( name );
211 final String greatest_common_prefix = ForesterUtil.greatestCommonPrefix( ext_nodes_names, separator );
212 return greatest_common_prefix;
215 private final static String obtainConfidence( final PhylogenyNode n ) {
216 if ( ( n.getBranchData().getConfidences() != null ) && ( n.getBranchData().getConfidences().size() > 0 ) ) {
217 final List<Confidence> confidences = n.getBranchData().getConfidences();
218 boolean not_first = false;
219 Collections.sort( confidences );
220 final StringBuilder sb = new StringBuilder();
221 for( final Confidence confidence : confidences ) {
222 final double value = confidence.getValue();
223 if ( value != Confidence.CONFIDENCE_DEFAULT_VALUE ) {
230 sb.append( ( ForesterUtil.isEmpty( confidence.getType() ) ? "confidence: "
231 : confidence.getType() + ": " ) + value );
234 return sb.toString();
239 public final static void performMapping( final Pattern pattern,
240 final SortedMap<String, String> map,
242 final boolean verbose )
243 throws UserException {
245 System.out.println();
246 System.out.println( "Id to annotation mapping:" );
248 final PhylogenyNodeIterator it = p.iteratorExternalForward();
249 while ( it.hasNext() ) {
250 final PhylogenyNode node = it.next();
251 final String name = node.getName().trim();
252 if ( ForesterUtil.isEmpty( name ) ) {
253 throw new UserException( "external node with empty name found" );
255 final Matcher m = pattern.matcher( name );
257 if ( !map.containsKey( name ) ) {
258 throw new UserException( "no mapping for \"" + name + "\" found" );
260 node.setName( map.get( name ).trim() );
262 System.out.println( name + " -> " + node.getName() );
267 System.out.println();
271 public final static void performExtraProcessing1( final Pattern pattern,
273 final String extra_sep,
275 final String annotation_sep,
276 final boolean verbose )
277 throws UserException {
279 System.out.println();
280 System.out.println( "Extra annotation processing:" );
282 final PhylogenyNodeIterator it = p.iteratorExternalForward();
283 while ( it.hasNext() ) {
284 final PhylogenyNode node = it.next();
285 final String name = node.getName().trim();
286 if ( ForesterUtil.isEmpty( name ) ) {
287 throw new UserException( "external node with empty name found" );
289 final Matcher m = pattern.matcher( name );
291 final StringBuilder sb = new StringBuilder();
292 final int last_index = name.lastIndexOf( extra_sep );
293 if ( last_index >= 0 ) {
294 final String annotation = name.substring( last_index + 1 ).trim();
295 if ( ForesterUtil.isEmptyTrimmed( annotation ) ) {
296 throw new UserException( "illegal format:" + name );
299 final String extra = name.substring( 0, last_index ).trim();
300 sb.append( annotation );
301 if ( !ForesterUtil.isEmpty( extra ) ) {
302 sb.append( annotation_sep );
307 sb.append( annotation );
309 node.setName( sb.toString() );
311 System.out.println( name + " -> " + node.getName() );
317 System.out.println();