in progress...
[jalview.git] / forester / java / src / org / forester / analysis / AncestralTaxonomyInference.java
1 // forester -- software libraries and applications
2 // for genomics and evolutionary biology research.
3 //
4 // Copyright (C) 2010 Christian M Zmasek
5 // Copyright (C) 2010 Sanford-Burnham Medical Research Institute
6 // All rights reserved
7 //
8 // This library is free software; you can redistribute it and/or
9 // modify it under the terms of the GNU Lesser General Public
10 // License as published by the Free Software Foundation; either
11 // version 2.1 of the License, or (at your option) any later version.
12 //
13 // This library is distributed in the hope that it will be useful,
14 // but WITHOUT ANY WARRANTY; without even the implied warranty of
15 // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
16 // Lesser General Public License for more details.
17 //
18 // You should have received a copy of the GNU Lesser General Public
19 // License along with this library; if not, write to the Free Software
20 // Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA
21 //
22 // Contact: phylosoft @ gmail . com
23 // WWW: www.phylosoft.org/forester
24
25 package org.forester.analysis;
26
27 import java.io.IOException;
28 import java.util.ArrayList;
29 import java.util.HashMap;
30 import java.util.List;
31 import java.util.SortedSet;
32 import java.util.TreeSet;
33
34 import org.forester.io.parsers.phyloxml.PhyloXmlDataFormatException;
35 import org.forester.phylogeny.Phylogeny;
36 import org.forester.phylogeny.PhylogenyNode;
37 import org.forester.phylogeny.data.Identifier;
38 import org.forester.phylogeny.data.Taxonomy;
39 import org.forester.phylogeny.iterators.PhylogenyNodeIterator;
40 import org.forester.util.ForesterUtil;
41 import org.forester.ws.uniprot.UniProtTaxonomy;
42 import org.forester.ws.uniprot.UniProtWsTools;
43
44 public final class AncestralTaxonomyInference {
45
46     private static final int                              MAX_CACHE_SIZE           = 100000;
47     private static final int                              MAX_TAXONOMIES_TO_RETURN = 100;
48     private static final HashMap<String, UniProtTaxonomy> _sn_up_cache_map         = new HashMap<String, UniProtTaxonomy>();
49     private static final HashMap<String, UniProtTaxonomy> _code_up_cache_map       = new HashMap<String, UniProtTaxonomy>();
50     private static final HashMap<String, UniProtTaxonomy> _cn_up_cache_map         = new HashMap<String, UniProtTaxonomy>();
51     private static final HashMap<String, UniProtTaxonomy> _id_up_cache_map         = new HashMap<String, UniProtTaxonomy>();
52
53     synchronized private static void clearCachesIfTooLarge() {
54         if ( getSnTaxCacheMap().size() > MAX_CACHE_SIZE ) {
55             getSnTaxCacheMap().clear();
56         }
57         if ( getCnTaxCacheMap().size() > MAX_CACHE_SIZE ) {
58             getCnTaxCacheMap().clear();
59         }
60         if ( getCodeTaxCacheMap().size() > MAX_CACHE_SIZE ) {
61             getCodeTaxCacheMap().clear();
62         }
63         if ( getIdTaxCacheMap().size() > MAX_CACHE_SIZE ) {
64             getIdTaxCacheMap().clear();
65         }
66     }
67
68     synchronized private static HashMap<String, UniProtTaxonomy> getCnTaxCacheMap() {
69         return _cn_up_cache_map;
70     }
71
72     synchronized private static HashMap<String, UniProtTaxonomy> getCodeTaxCacheMap() {
73         return _code_up_cache_map;
74     }
75
76     synchronized private static HashMap<String, UniProtTaxonomy> getIdTaxCacheMap() {
77         return _id_up_cache_map;
78     }
79
80     synchronized private static HashMap<String, UniProtTaxonomy> getSnTaxCacheMap() {
81         return _sn_up_cache_map;
82     }
83
84     synchronized private static UniProtTaxonomy getTaxonomies( final HashMap<String, UniProtTaxonomy> cache,
85                                                                final String query,
86                                                                final QUERY_TYPE qt ) throws IOException {
87         if ( cache.containsKey( query ) ) {
88             return cache.get( query ).copy();
89         }
90         else {
91             List<UniProtTaxonomy> up_taxonomies = null;
92             switch ( qt ) {
93                 case ID:
94                     up_taxonomies = getTaxonomiesFromId( query );
95                     break;
96                 case CODE:
97                     up_taxonomies = getTaxonomiesFromTaxonomyCode( query );
98                     break;
99                 case SN:
100                     up_taxonomies = getTaxonomiesFromScientificName( query );
101                     break;
102                 case CN:
103                     up_taxonomies = getTaxonomiesFromCommonName( query );
104                     break;
105                 default:
106                     throw new RuntimeException();
107             }
108             if ( ( up_taxonomies != null ) && ( up_taxonomies.size() == 1 ) ) {
109                 final UniProtTaxonomy up_tax = up_taxonomies.get( 0 );
110                 if ( !ForesterUtil.isEmpty( up_tax.getScientificName() ) ) {
111                     getSnTaxCacheMap().put( up_tax.getScientificName(), up_tax );
112                 }
113                 if ( !ForesterUtil.isEmpty( up_tax.getCode() ) ) {
114                     getCodeTaxCacheMap().put( up_tax.getCode(), up_tax );
115                 }
116                 if ( !ForesterUtil.isEmpty( up_tax.getCommonName() ) ) {
117                     getCnTaxCacheMap().put( up_tax.getCommonName(), up_tax );
118                 }
119                 if ( !ForesterUtil.isEmpty( up_tax.getId() ) ) {
120                     getIdTaxCacheMap().put( up_tax.getId(), up_tax );
121                 }
122                 return up_tax;
123             }
124             else {
125                 return null;
126             }
127         }
128     }
129
130     synchronized private static List<UniProtTaxonomy> getTaxonomiesFromCommonName( final String query )
131             throws IOException {
132         return UniProtWsTools.getTaxonomiesFromCommonNameStrict( query, MAX_TAXONOMIES_TO_RETURN );
133     }
134
135     synchronized private static List<UniProtTaxonomy> getTaxonomiesFromId( final String query ) throws IOException {
136         return UniProtWsTools.getTaxonomiesFromId( query, MAX_TAXONOMIES_TO_RETURN );
137     }
138
139     synchronized private static List<UniProtTaxonomy> getTaxonomiesFromScientificName( final String query )
140             throws IOException {
141         return UniProtWsTools.getTaxonomiesFromScientificNameStrict( query, MAX_TAXONOMIES_TO_RETURN );
142     }
143
144     synchronized private static List<UniProtTaxonomy> getTaxonomiesFromTaxonomyCode( final String query )
145             throws IOException {
146         return UniProtWsTools.getTaxonomiesFromTaxonomyCode( query, MAX_TAXONOMIES_TO_RETURN );
147     }
148
149     synchronized public static SortedSet<String> inferTaxonomyFromDescendents( final Phylogeny phy ) throws IOException {
150         clearCachesIfTooLarge();
151         final SortedSet<String> not_found = new TreeSet<String>();
152         for( final PhylogenyNodeIterator iter = phy.iteratorPostorder(); iter.hasNext(); ) {
153             final PhylogenyNode node = iter.next();
154             // final QUERY_TYPE qt = null;
155             // Taxonomy tax = null;
156             // if ( node.getNodeData().isHasTaxonomy() ) {
157             // tax = node.getNodeData().getTaxonomy();
158             // }
159             // UniProtTaxonomy up_tax = null;
160             // if ( ( tax != null )
161             // && ( isHasAppropriateId( tax ) || !ForesterUtil.isEmpty(
162             // tax.getScientificName() )
163             // || !ForesterUtil.isEmpty( tax.getTaxonomyCode() ) ||
164             // !ForesterUtil.isEmpty( tax
165             // .getCommonName() ) ) ) {
166             // final String query = null;
167             // up_tax = obtainUniProtTaxonomy( tax, query, qt );
168             // if ( up_tax == null ) {
169             // not_found.add( query );
170             // }
171             // else {
172             // updateTaxonomy( qt, node, tax, up_tax );
173             // }
174             // }
175             if ( !node.isExternal() ) {
176                 inferTaxonomyFromDescendents( node, not_found );
177             }
178         }
179         return not_found;
180     }
181
182     synchronized private static void inferTaxonomyFromDescendents( final PhylogenyNode n,
183                                                                    final SortedSet<String> not_found )
184             throws IOException {
185         if ( n.isExternal() ) {
186             throw new IllegalArgumentException( "attempt to infer taxonomy from descendants of external node" );
187         }
188         n.getNodeData().setTaxonomy( null );
189         final List<PhylogenyNode> descs = n.getDescendants();
190         final List<String[]> lineages = new ArrayList<String[]>();
191         int shortest_lin_length = Integer.MAX_VALUE;
192         for( final PhylogenyNode desc : descs ) {
193             if ( desc.getNodeData().isHasTaxonomy()
194                     && ( isHasAppropriateId( desc.getNodeData().getTaxonomy() )
195                             || !ForesterUtil.isEmpty( desc.getNodeData().getTaxonomy().getScientificName() )
196                             || !ForesterUtil.isEmpty( desc.getNodeData().getTaxonomy().getTaxonomyCode() ) || !ForesterUtil
197                             .isEmpty( desc.getNodeData().getTaxonomy().getCommonName() ) ) ) {
198                 final QUERY_TYPE qt = null;
199                 final String query = null;
200                 final UniProtTaxonomy up_tax = obtainUniProtTaxonomy( desc.getNodeData().getTaxonomy(), query, qt );
201                 String[] lineage = null;
202                 if ( up_tax != null ) {
203                     lineage = obtainLineagePlusOwnScientificName( up_tax );
204                 }
205                 if ( ( lineage == null ) || ( lineage.length < 1 ) ) {
206                     not_found.add( desc.getNodeData().getTaxonomy().asText().toString() );
207                     return;
208                 }
209                 if ( lineage.length < shortest_lin_length ) {
210                     shortest_lin_length = lineage.length;
211                 }
212                 lineages.add( lineage );
213             }
214             else {
215                 String msg = "Node(s) with no or inappropriate taxonomic information found";
216                 if ( !ForesterUtil.isEmpty( desc.getName() ) ) {
217                     msg = "Node " + desc.getName() + " has no or inappropriate taxonomic information";
218                 }
219                 throw new IllegalArgumentException( msg );
220             }
221         }
222         String last_common_lineage = null;
223         if ( shortest_lin_length > 0 ) {
224             I: for( int i = 0; i < shortest_lin_length; ++i ) {
225                 final String lineage_0 = lineages.get( 0 )[ i ];
226                 for( int j = 1; j < lineages.size(); ++j ) {
227                     if ( !lineage_0.equals( lineages.get( j )[ i ] ) ) {
228                         break I;
229                     }
230                 }
231                 last_common_lineage = lineage_0;
232             }
233         }
234         if ( last_common_lineage == null ) {
235             return;
236         }
237         // if ( !n.getNodeData().isHasTaxonomy() ) {
238         // n.getNodeData().setTaxonomy( new Taxonomy() );
239         // }
240         final Taxonomy tax = new Taxonomy();
241         n.getNodeData().setTaxonomy( tax );
242         tax.setScientificName( last_common_lineage );
243         final UniProtTaxonomy up_tax = obtainUniProtTaxonomyFromSn( last_common_lineage );
244         if ( up_tax != null ) {
245             if ( !ForesterUtil.isEmpty( up_tax.getRank() ) ) {
246                 try {
247                     tax.setRank( up_tax.getRank().toLowerCase() );
248                 }
249                 catch ( final PhyloXmlDataFormatException ex ) {
250                     tax.setRank( "" );
251                 }
252             }
253             if ( !ForesterUtil.isEmpty( up_tax.getId() ) ) {
254                 tax.setIdentifier( new Identifier( up_tax.getId(), "uniprot" ) );
255             }
256             if ( !ForesterUtil.isEmpty( up_tax.getCommonName() ) ) {
257                 tax.setCommonName( up_tax.getCommonName() );
258             }
259             if ( !ForesterUtil.isEmpty( up_tax.getSynonym() ) && !tax.getSynonyms().contains( up_tax.getSynonym() ) ) {
260                 tax.getSynonyms().add( up_tax.getSynonym() );
261             }
262         }
263         for( final PhylogenyNode desc : descs ) {
264             if ( !desc.isExternal() && desc.getNodeData().isHasTaxonomy()
265                     && desc.getNodeData().getTaxonomy().isEqual( tax ) ) {
266                 desc.getNodeData().setTaxonomy( null );
267             }
268         }
269     }
270
271     synchronized private static boolean isHasAppropriateId( final Taxonomy tax ) {
272         return ( ( tax.getIdentifier() != null ) && ( !ForesterUtil.isEmpty( tax.getIdentifier().getValue() ) && ( tax
273                 .getIdentifier().getProvider().equalsIgnoreCase( "ncbi" )
274                 || tax.getIdentifier().getProvider().equalsIgnoreCase( "uniprot" ) || tax.getIdentifier().getProvider()
275                 .equalsIgnoreCase( "uniprotkb" ) ) ) );
276     }
277
278     synchronized public static SortedSet<String> obtainDetailedTaxonomicInformation( final Phylogeny phy )
279             throws IOException {
280         clearCachesIfTooLarge();
281         final SortedSet<String> not_found = new TreeSet<String>();
282         for( final PhylogenyNodeIterator iter = phy.iteratorPostorder(); iter.hasNext(); ) {
283             final PhylogenyNode node = iter.next();
284             final QUERY_TYPE qt = null;
285             Taxonomy tax = null;
286             if ( node.getNodeData().isHasTaxonomy() ) {
287                 tax = node.getNodeData().getTaxonomy();
288             }
289             else if ( node.isExternal() ) {
290                 if ( !ForesterUtil.isEmpty( node.getName() ) ) {
291                     not_found.add( node.getName() );
292                 }
293                 else {
294                     not_found.add( node.toString() );
295                 }
296             }
297             UniProtTaxonomy up_tax = null;
298             if ( ( tax != null )
299                     && ( isHasAppropriateId( tax ) || !ForesterUtil.isEmpty( tax.getScientificName() )
300                             || !ForesterUtil.isEmpty( tax.getTaxonomyCode() ) || !ForesterUtil.isEmpty( tax
301                             .getCommonName() ) ) ) {
302                 up_tax = obtainUniProtTaxonomy( tax, null, qt );
303                 if ( up_tax != null ) {
304                     updateTaxonomy( qt, node, tax, up_tax );
305                 }
306                 else {
307                     not_found.add( tax.toString() );
308                 }
309             }
310         }
311         return not_found;
312     }
313
314     synchronized private static String[] obtainLineagePlusOwnScientificName( final UniProtTaxonomy up_tax ) {
315         final String[] lineage = up_tax.getLineage();
316         final String[] lin_plus_self = new String[ lineage.length + 1 ];
317         for( int i = 0; i < lineage.length; ++i ) {
318             lin_plus_self[ i ] = lineage[ i ];
319         }
320         lin_plus_self[ lineage.length ] = up_tax.getScientificName();
321         return lin_plus_self;
322     }
323
324     synchronized private static UniProtTaxonomy obtainUniProtTaxonomy( final Taxonomy tax, String query, QUERY_TYPE qt )
325             throws IOException {
326         if ( isHasAppropriateId( tax ) ) {
327             query = tax.getIdentifier().getValue();
328             qt = QUERY_TYPE.ID;
329             return getTaxonomies( getIdTaxCacheMap(), query, qt );
330         }
331         else if ( !ForesterUtil.isEmpty( tax.getScientificName() ) ) {
332             query = tax.getScientificName();
333             qt = QUERY_TYPE.SN;
334             return getTaxonomies( getSnTaxCacheMap(), query, qt );
335         }
336         else if ( !ForesterUtil.isEmpty( tax.getTaxonomyCode() ) ) {
337             query = tax.getTaxonomyCode();
338             qt = QUERY_TYPE.CODE;
339             return getTaxonomies( getCodeTaxCacheMap(), query, qt );
340         }
341         else {
342             query = tax.getCommonName();
343             qt = QUERY_TYPE.CN;
344             return getTaxonomies( getCnTaxCacheMap(), query, qt );
345         }
346     }
347
348     synchronized private static UniProtTaxonomy obtainUniProtTaxonomyFromSn( final String sn ) throws IOException {
349         UniProtTaxonomy up_tax = null;
350         if ( getSnTaxCacheMap().containsKey( sn ) ) {
351             up_tax = getSnTaxCacheMap().get( sn ).copy();
352         }
353         else {
354             final List<UniProtTaxonomy> up_taxonomies = getTaxonomiesFromScientificName( sn );
355             if ( ( up_taxonomies != null ) && ( up_taxonomies.size() == 1 ) ) {
356                 up_tax = up_taxonomies.get( 0 );
357                 getSnTaxCacheMap().put( sn, up_tax );
358                 if ( !ForesterUtil.isEmpty( up_tax.getCode() ) ) {
359                     getCodeTaxCacheMap().put( up_tax.getCode(), up_tax );
360                 }
361                 if ( !ForesterUtil.isEmpty( up_tax.getCommonName() ) ) {
362                     getCnTaxCacheMap().put( up_tax.getCommonName(), up_tax );
363                 }
364                 if ( !ForesterUtil.isEmpty( up_tax.getId() ) ) {
365                     getIdTaxCacheMap().put( up_tax.getId(), up_tax );
366                 }
367             }
368         }
369         return up_tax;
370     }
371
372     synchronized private static void updateTaxonomy( final QUERY_TYPE qt,
373                                                      final PhylogenyNode node,
374                                                      final Taxonomy tax,
375                                                      final UniProtTaxonomy up_tax ) {
376         if ( ( qt != QUERY_TYPE.SN ) && !ForesterUtil.isEmpty( up_tax.getScientificName() )
377                 && ForesterUtil.isEmpty( tax.getScientificName() ) ) {
378             tax.setScientificName( up_tax.getScientificName() );
379         }
380         if ( node.isExternal()
381                 && ( ( qt != QUERY_TYPE.CODE ) && !ForesterUtil.isEmpty( up_tax.getCode() ) && ForesterUtil
382                         .isEmpty( tax.getTaxonomyCode() ) ) ) {
383             tax.setTaxonomyCode( up_tax.getCode() );
384         }
385         if ( ( qt != QUERY_TYPE.CN ) && !ForesterUtil.isEmpty( up_tax.getCommonName() )
386                 && ForesterUtil.isEmpty( tax.getCommonName() ) ) {
387             tax.setCommonName( up_tax.getCommonName() );
388         }
389         if ( !ForesterUtil.isEmpty( up_tax.getSynonym() ) && !tax.getSynonyms().contains( up_tax.getSynonym() ) ) {
390             tax.getSynonyms().add( up_tax.getSynonym() );
391         }
392         if ( !ForesterUtil.isEmpty( up_tax.getRank() ) && ForesterUtil.isEmpty( tax.getRank() ) ) {
393             try {
394                 tax.setRank( up_tax.getRank().toLowerCase() );
395             }
396             catch ( final PhyloXmlDataFormatException ex ) {
397                 tax.setRank( "" );
398             }
399         }
400         if ( ( qt != QUERY_TYPE.ID ) && !ForesterUtil.isEmpty( up_tax.getId() ) && ( tax.getIdentifier() == null ) ) {
401             tax.setIdentifier( new Identifier( up_tax.getId(), "uniprot" ) );
402         }
403     }
404
405     private enum QUERY_TYPE {
406         CODE, SN, CN, ID;
407     }
408 }