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.archaeopteryx.tools.AncestralTaxonomyInferenceException;
  35 import org.forester.io.parsers.phyloxml.PhyloXmlDataFormatException;
  36 import org.forester.phylogeny.Phylogeny;
  37 import org.forester.phylogeny.PhylogenyNode;
  38 import org.forester.phylogeny.data.Identifier;
  39 import org.forester.phylogeny.data.Taxonomy;
  40 import org.forester.phylogeny.iterators.PhylogenyNodeIterator;
  41 import org.forester.util.ForesterUtil;
  42 import org.forester.ws.uniprot.UniProtTaxonomy;
  43 import org.forester.ws.uniprot.UniProtWsTools;
  44
  45 public final class AncestralTaxonomyInference {
  46
  47     private static final int                              MAX_CACHE_SIZE           = 100000;
  48     private static final int                              MAX_TAXONOMIES_TO_RETURN = 100;
  49     private static final HashMap<String, UniProtTaxonomy> _sn_up_cache_map         = new HashMap<String, UniProtTaxonomy>();
  50     private static final HashMap<String, UniProtTaxonomy> _code_up_cache_map       = new HashMap<String, UniProtTaxonomy>();
  51     private static final HashMap<String, UniProtTaxonomy> _cn_up_cache_map         = new HashMap<String, UniProtTaxonomy>();
  52     private static final HashMap<String, UniProtTaxonomy> _id_up_cache_map         = new HashMap<String, UniProtTaxonomy>();
  53
  54     synchronized private static void clearCachesIfTooLarge() {
  55         if ( getSnTaxCacheMap().size() > MAX_CACHE_SIZE ) {
  56             getSnTaxCacheMap().clear();
  57         }
  58         if ( getCnTaxCacheMap().size() > MAX_CACHE_SIZE ) {
  59             getCnTaxCacheMap().clear();
  60         }
  61         if ( getCodeTaxCacheMap().size() > MAX_CACHE_SIZE ) {
  62             getCodeTaxCacheMap().clear();
  63         }
  64         if ( getIdTaxCacheMap().size() > MAX_CACHE_SIZE ) {
  65             getIdTaxCacheMap().clear();
  66         }
  67     }
  68
  69     synchronized private static HashMap<String, UniProtTaxonomy> getCnTaxCacheMap() {
  70         return _cn_up_cache_map;
  71     }
  72
  73     synchronized private static HashMap<String, UniProtTaxonomy> getCodeTaxCacheMap() {
  74         return _code_up_cache_map;
  75     }
  76
  77     synchronized private static HashMap<String, UniProtTaxonomy> getIdTaxCacheMap() {
  78         return _id_up_cache_map;
  79     }
  80
  81     synchronized private static HashMap<String, UniProtTaxonomy> getSnTaxCacheMap() {
  82         return _sn_up_cache_map;
  83     }
  84
  85     synchronized private static UniProtTaxonomy getTaxonomies( final HashMap<String, UniProtTaxonomy> cache,
  86                                                                final String query,
  87                                                                final QUERY_TYPE qt ) throws IOException {
  88         if ( cache.containsKey( query ) ) {
  89             return cache.get( query ).copy();
  90         }
  91         else {
  92             List<UniProtTaxonomy> up_taxonomies = null;
  93             switch ( qt ) {
  94                 case ID:
  95                     up_taxonomies = getTaxonomiesFromId( query );
  96                     break;
  97                 case CODE:
  98                     up_taxonomies = getTaxonomiesFromTaxonomyCode( query );
  99                     break;
 100                 case SN:
 101                     up_taxonomies = getTaxonomiesFromScientificName( query );
 102                     break;
 103                 case CN:
 104                     up_taxonomies = getTaxonomiesFromCommonName( query );
 105                     break;
 106                 default:
 107                     throw new RuntimeException();
 108             }
 109             if ( ( up_taxonomies != null ) && ( up_taxonomies.size() == 1 ) ) {
 110                 final UniProtTaxonomy up_tax = up_taxonomies.get( 0 );
 111                 if ( !ForesterUtil.isEmpty( up_tax.getScientificName() ) ) {
 112                     getSnTaxCacheMap().put( up_tax.getScientificName(), up_tax );
 113                 }
 114                 if ( !ForesterUtil.isEmpty( up_tax.getCode() ) ) {
 115                     getCodeTaxCacheMap().put( up_tax.getCode(), up_tax );
 116                 }
 117                 if ( !ForesterUtil.isEmpty( up_tax.getCommonName() ) ) {
 118                     getCnTaxCacheMap().put( up_tax.getCommonName(), up_tax );
 119                 }
 120                 if ( !ForesterUtil.isEmpty( up_tax.getId() ) ) {
 121                     getIdTaxCacheMap().put( up_tax.getId(), up_tax );
 122                 }
 123                 return up_tax;
 124             }
 125             else {
 126                 return null;
 127             }
 128         }
 129     }
 130
 131     synchronized private static List<UniProtTaxonomy> getTaxonomiesFromCommonName( final String query )
 132             throws IOException {
 133         return UniProtWsTools.getTaxonomiesFromCommonNameStrict( query, MAX_TAXONOMIES_TO_RETURN );
 134     }
 135
 136     synchronized private static List<UniProtTaxonomy> getTaxonomiesFromId( final String query ) throws IOException {
 137         return UniProtWsTools.getTaxonomiesFromId( query, MAX_TAXONOMIES_TO_RETURN );
 138     }
 139
 140     synchronized private static List<UniProtTaxonomy> getTaxonomiesFromScientificName( final String query )
 141             throws IOException {
 142         return UniProtWsTools.getTaxonomiesFromScientificNameStrict( query, MAX_TAXONOMIES_TO_RETURN );
 143     }
 144
 145     synchronized private static List<UniProtTaxonomy> getTaxonomiesFromTaxonomyCode( final String query )
 146             throws IOException {
 147         return UniProtWsTools.getTaxonomiesFromTaxonomyCode( query, MAX_TAXONOMIES_TO_RETURN );
 148     }
 149
 150     synchronized public static void inferTaxonomyFromDescendents( final Phylogeny phy ) throws IOException,
 151             AncestralTaxonomyInferenceException {
 152         clearCachesIfTooLarge();
 153         for( final PhylogenyNodeIterator iter = phy.iteratorPostorder(); iter.hasNext(); ) {
 154             final PhylogenyNode node = iter.next();
 155             if ( !node.isExternal() ) {
 156                 inferTaxonomyFromDescendents( node );
 157             }
 158         }
 159     }
 160
 161     synchronized private static void inferTaxonomyFromDescendents( final PhylogenyNode n ) throws IOException,
 162             AncestralTaxonomyInferenceException {
 163         if ( n.isExternal() ) {
 164             throw new IllegalArgumentException( "attempt to infer taxonomy from descendants of external node" );
 165         }
 166         n.getNodeData().setTaxonomy( null );
 167         final List<PhylogenyNode> descs = n.getDescendants();
 168         final List<String[]> lineages = new ArrayList<String[]>();
 169         int shortest_lin_length = Integer.MAX_VALUE;
 170         for( final PhylogenyNode desc : descs ) {
 171             if ( desc.getNodeData().isHasTaxonomy()
 172                     && ( isHasAppropriateId( desc.getNodeData().getTaxonomy() )
 173                             || !ForesterUtil.isEmpty( desc.getNodeData().getTaxonomy().getScientificName() )
 174                             || !ForesterUtil.isEmpty( desc.getNodeData().getTaxonomy().getTaxonomyCode() ) || !ForesterUtil
 175                             .isEmpty( desc.getNodeData().getTaxonomy().getCommonName() ) ) ) {
 176                 final UniProtTaxonomy up_tax = obtainUniProtTaxonomy( desc.getNodeData().getTaxonomy(), null, null );
 177                 String[] lineage = null;
 178                 if ( up_tax != null ) {
 179                     lineage = up_tax.getLineageAsArray();
 180                 }
 181                 if ( ( lineage == null ) || ( lineage.length < 1 ) ) {
 182                     throw new AncestralTaxonomyInferenceException( "a taxonomic lineage for node \""
 183                             + desc.getNodeData().getTaxonomy().toString() + "\" could not be found" );
 184                 }
 185                 if ( lineage.length < shortest_lin_length ) {
 186                     shortest_lin_length = lineage.length;
 187                 }
 188                 lineages.add( lineage );
 189             }
 190             else {
 191                 String node = "";
 192                 if ( !ForesterUtil.isEmpty( desc.getName() ) ) {
 193                     node = "\"" + desc.getName() + "\"";
 194                 }
 195                 else {
 196                     node = "[" + desc.getId() + "]";
 197                 }
 198                 //   final List<PhylogenyNode> e = desc.getAllExternalDescendants();
 199                 //TODO remove me!
 200                 //                System.out.println();
 201                 //                int x = 0;
 202                 //                for( final PhylogenyNode object : e ) {
 203                 //                    System.out.println( x + ":" );
 204                 //                    System.out.println( object.getName() + "  " );
 205                 //                    x++;
 206                 //                }
 207                 //                System.out.println();
 208                 //
 209                 throw new AncestralTaxonomyInferenceException( "node " + node
 210                         + " has no or inappropriate taxonomic information" );
 211             }
 212         }
 213         final List<String> last_common_lineage = new ArrayList<String>();
 214         String last_common = null;
 215         if ( shortest_lin_length > 0 ) {
 216             I: for( int i = 0; i < shortest_lin_length; ++i ) {
 217                 final String lineage_0 = lineages.get( 0 )[ i ];
 218                 for( int j = 1; j < lineages.size(); ++j ) {
 219                     if ( !lineage_0.equals( lineages.get( j )[ i ] ) ) {
 220                         break I;
 221                     }
 222                 }
 223                 // last_common_lineage = lineage_0;
 224                 last_common_lineage.add( lineage_0 );
 225                 last_common = lineage_0;
 226             }
 227         }
 228         // if ( last_common_lineage == null ) {
 229         if ( last_common_lineage.isEmpty() ) {
 230             String msg = "no common lineage for:\n";
 231             int counter = 0;
 232             for( final String[] strings : lineages ) {
 233                 msg += counter + ": ";
 234                 ++counter;
 235                 for( final String string : strings ) {
 236                     msg += string + " ";
 237                 }
 238                 msg += "\n";
 239             }
 240             throw new AncestralTaxonomyInferenceException( msg );
 241         }
 242         final Taxonomy tax = new Taxonomy();
 243         n.getNodeData().setTaxonomy( tax );
 244         tax.setScientificName( last_common );
 245         final UniProtTaxonomy up_tax = obtainUniProtTaxonomyFromCommonLineage( last_common_lineage );
 246         if ( up_tax != null ) {
 247             if ( !ForesterUtil.isEmpty( up_tax.getRank() ) ) {
 248                 try {
 249                     tax.setRank( up_tax.getRank().toLowerCase() );
 250                 }
 251                 catch ( final PhyloXmlDataFormatException ex ) {
 252                     tax.setRank( "" );
 253                 }
 254             }
 255             if ( !ForesterUtil.isEmpty( up_tax.getId() ) ) {
 256                 tax.setIdentifier( new Identifier( up_tax.getId(), "uniprot" ) );
 257             }
 258             if ( !ForesterUtil.isEmpty( up_tax.getCommonName() ) ) {
 259                 tax.setCommonName( up_tax.getCommonName() );
 260             }
 261             if ( !ForesterUtil.isEmpty( up_tax.getSynonym() ) && !tax.getSynonyms().contains( up_tax.getSynonym() ) ) {
 262                 tax.getSynonyms().add( up_tax.getSynonym() );
 263             }
 264             if ( up_tax.getLineage() != null ) {
 265                 tax.setLineage( new ArrayList<String>() );
 266                 for( final String lin : up_tax.getLineage() ) {
 267                     if ( !ForesterUtil.isEmpty( lin ) ) {
 268                         tax.getLineage().add( lin );
 269                     }
 270                 }
 271             }
 272         }
 273         for( final PhylogenyNode desc : descs ) {
 274             if ( !desc.isExternal() && desc.getNodeData().isHasTaxonomy()
 275                     && desc.getNodeData().getTaxonomy().isEqual( tax ) ) {
 276                 desc.getNodeData().setTaxonomy( null );
 277             }
 278         }
 279     }
 280
 281     synchronized private static boolean isHasAppropriateId( final Taxonomy tax ) {
 282         return ( ( tax.getIdentifier() != null ) && ( !ForesterUtil.isEmpty( tax.getIdentifier().getValue() ) && ( tax
 283                 .getIdentifier().getProvider().equalsIgnoreCase( "ncbi" )
 284                 || tax.getIdentifier().getProvider().equalsIgnoreCase( "uniprot" ) || tax.getIdentifier().getProvider()
 285                 .equalsIgnoreCase( "uniprotkb" ) ) ) );
 286     }
 287
 288     synchronized public static SortedSet<String> obtainDetailedTaxonomicInformation( final Phylogeny phy,
 289                                                                                      final boolean delete )
 290             throws IOException {
 291         clearCachesIfTooLarge();
 292         final SortedSet<String> not_found = new TreeSet<String>();
 293         List<PhylogenyNode> not_found_external_nodes = null;
 294         if ( delete ) {
 295             not_found_external_nodes = new ArrayList<PhylogenyNode>();
 296         }
 297         for( final PhylogenyNodeIterator iter = phy.iteratorPostorder(); iter.hasNext(); ) {
 298             final PhylogenyNode node = iter.next();
 299             final QUERY_TYPE qt = null;
 300             Taxonomy tax = null;
 301             if ( node.getNodeData().isHasTaxonomy() ) {
 302                 tax = node.getNodeData().getTaxonomy();
 303             }
 304             else if ( node.isExternal() ) {
 305                 if ( !ForesterUtil.isEmpty( node.getName() ) ) {
 306                     not_found.add( node.getName() );
 307                 }
 308                 else {
 309                     not_found.add( node.toString() );
 310                 }
 311                 if ( delete ) {
 312                     not_found_external_nodes.add( node );
 313                 }
 314             }
 315             UniProtTaxonomy uniprot_tax = null;
 316             if ( ( tax != null )
 317                     && ( isHasAppropriateId( tax ) || !ForesterUtil.isEmpty( tax.getScientificName() )
 318                             || !ForesterUtil.isEmpty( tax.getTaxonomyCode() ) || !ForesterUtil.isEmpty( tax
 319                             .getCommonName() ) ) ) {
 320                 uniprot_tax = obtainUniProtTaxonomy( tax, null, qt );
 321                 if ( uniprot_tax != null ) {
 322                     updateTaxonomy( qt, node, tax, uniprot_tax );
 323                 }
 324                 else {
 325                     not_found.add( tax.toString() );
 326                     if ( delete && node.isExternal() ) {
 327                         not_found_external_nodes.add( node );
 328                     }
 329                 }
 330             }
 331         }
 332         if ( delete ) {
 333             for( final PhylogenyNode node : not_found_external_nodes ) {
 334                 phy.deleteSubtree( node, true );
 335             }
 336             phy.externalNodesHaveChanged();
 337             phy.hashIDs();
 338             phy.recalculateNumberOfExternalDescendants( true );
 339         }
 340         return not_found;
 341     }
 342
 343     // TODO this might not be needed anymore
 344     //  synchronized private static String[] obtainLineagePlusOwnScientificName( final UniProtTaxonomy up_tax ) {
 345     //      final String[] lineage = up_tax.getLineageAsArray();
 346     //      final String[] lin_plus_self = new String[ lineage.length + 1 ];
 347     //      for( int i = 0; i < lineage.length; ++i ) {
 348     //          lin_plus_self[ i ] = lineage[ i ];
 349     //      }
 350     //      lin_plus_self[ lineage.length ] = up_tax.getScientificName();
 351     //      return lin_plus_self;
 352     //  }
 353     synchronized private static UniProtTaxonomy obtainUniProtTaxonomy( final Taxonomy tax, String query, QUERY_TYPE qt )
 354             throws IOException {
 355         if ( isHasAppropriateId( tax ) ) {
 356             query = tax.getIdentifier().getValue();
 357             qt = QUERY_TYPE.ID;
 358             System.out.println( "query by id: " + query );
 359             return getTaxonomies( getIdTaxCacheMap(), query, qt );
 360         }
 361         else if ( !ForesterUtil.isEmpty( tax.getScientificName() ) ) {
 362             query = tax.getScientificName();
 363             qt = QUERY_TYPE.SN;
 364             System.out.println( "query by sn: " + query );
 365             return getTaxonomies( getSnTaxCacheMap(), query, qt );
 366         }
 367         else if ( !ForesterUtil.isEmpty( tax.getTaxonomyCode() ) ) {
 368             query = tax.getTaxonomyCode();
 369             qt = QUERY_TYPE.CODE;
 370             return getTaxonomies( getCodeTaxCacheMap(), query, qt );
 371         }
 372         else {
 373             query = tax.getCommonName();
 374             qt = QUERY_TYPE.CN;
 375             return getTaxonomies( getCnTaxCacheMap(), query, qt );
 376         }
 377     }
 378
 379     synchronized private static UniProtTaxonomy obtainUniProtTaxonomyFromSn( final String sn ) throws IOException {
 380         UniProtTaxonomy up_tax = null;
 381         if ( getSnTaxCacheMap().containsKey( sn ) ) {
 382             up_tax = getSnTaxCacheMap().get( sn ).copy();
 383         }
 384         else {
 385             final List<UniProtTaxonomy> up_taxonomies = getTaxonomiesFromScientificName( sn );
 386             if ( ( up_taxonomies != null ) && ( up_taxonomies.size() == 1 ) ) {
 387                 up_tax = up_taxonomies.get( 0 );
 388                 getSnTaxCacheMap().put( sn, up_tax );
 389                 if ( !ForesterUtil.isEmpty( up_tax.getCode() ) ) {
 390                     getCodeTaxCacheMap().put( up_tax.getCode(), up_tax );
 391                 }
 392                 if ( !ForesterUtil.isEmpty( up_tax.getCommonName() ) ) {
 393                     getCnTaxCacheMap().put( up_tax.getCommonName(), up_tax );
 394                 }
 395                 if ( !ForesterUtil.isEmpty( up_tax.getId() ) ) {
 396                     getIdTaxCacheMap().put( up_tax.getId(), up_tax );
 397                 }
 398             }
 399         }
 400         return up_tax;
 401     }
 402
 403     synchronized private static UniProtTaxonomy obtainUniProtTaxonomyFromCommonLineage( final List<String> lineage )
 404             throws AncestralTaxonomyInferenceException, IOException {
 405         UniProtTaxonomy up_tax = null;
 406         // -- if ( getSnTaxCacheMap().containsKey( sn ) ) {
 407         // --     up_tax = getSnTaxCacheMap().get( sn ).copy();
 408         // -- }
 409         //  else {
 410         final List<UniProtTaxonomy> up_taxonomies = getTaxonomiesFromScientificName( lineage.get( lineage.size() - 1 ) );
 411         //-- if ( ( up_taxonomies != null ) && ( up_taxonomies.size() == 1 ) ) {
 412         if ( ( up_taxonomies != null ) && ( up_taxonomies.size() > 0 ) ) {
 413             for( final UniProtTaxonomy up_taxonomy : up_taxonomies ) {
 414                 boolean match = true;
 415                 I: for( int i = 0; i < lineage.size(); ++i ) {
 416                     if ( !lineage.get( i ).equalsIgnoreCase( up_taxonomy.getLineage().get( i ) ) ) {
 417                         match = false;
 418                         break I;
 419                     }
 420                 }
 421                 if ( match ) {
 422                     if ( up_tax != null ) {
 423                         throw new AncestralTaxonomyInferenceException( "lineage \""
 424                                 + ForesterUtil.stringListToString( lineage, " > " ) + "\" is not unique" );
 425                     }
 426                     up_tax = up_taxonomy;
 427                 }
 428             }
 429             if ( up_tax == null ) {
 430                 throw new AncestralTaxonomyInferenceException( "lineage \""
 431                         + ForesterUtil.stringListToString( lineage, " > " ) + "\" not found" );
 432             }
 433             //-- up_tax = up_taxonomies.get( 0 );
 434             //-- getSnTaxCacheMap().put( sn, up_tax );
 435             if ( !ForesterUtil.isEmpty( up_tax.getCode() ) ) {
 436                 getCodeTaxCacheMap().put( up_tax.getCode(), up_tax );
 437             }
 438             if ( !ForesterUtil.isEmpty( up_tax.getCommonName() ) ) {
 439                 getCnTaxCacheMap().put( up_tax.getCommonName(), up_tax );
 440             }
 441             if ( !ForesterUtil.isEmpty( up_tax.getId() ) ) {
 442                 getIdTaxCacheMap().put( up_tax.getId(), up_tax );
 443             }
 444         }
 445         //  }
 446         return up_tax;
 447     }
 448
 449     synchronized private static void updateTaxonomy( final QUERY_TYPE qt,
 450                                                      final PhylogenyNode node,
 451                                                      final Taxonomy tax,
 452                                                      final UniProtTaxonomy up_tax ) {
 453         if ( ( qt != QUERY_TYPE.SN ) && !ForesterUtil.isEmpty( up_tax.getScientificName() )
 454                 && ForesterUtil.isEmpty( tax.getScientificName() ) ) {
 455             tax.setScientificName( up_tax.getScientificName() );
 456         }
 457         //  if ( node.isExternal()
 458         if ( ( qt != QUERY_TYPE.CODE ) && !ForesterUtil.isEmpty( up_tax.getCode() )
 459                 && ForesterUtil.isEmpty( tax.getTaxonomyCode() ) ) {
 460             tax.setTaxonomyCode( up_tax.getCode() );
 461         }
 462         if ( ( qt != QUERY_TYPE.CN ) && !ForesterUtil.isEmpty( up_tax.getCommonName() )
 463                 && ForesterUtil.isEmpty( tax.getCommonName() ) ) {
 464             tax.setCommonName( up_tax.getCommonName() );
 465         }
 466         if ( !ForesterUtil.isEmpty( up_tax.getSynonym() ) && !tax.getSynonyms().contains( up_tax.getSynonym() ) ) {
 467             tax.getSynonyms().add( up_tax.getSynonym() );
 468         }
 469         if ( !ForesterUtil.isEmpty( up_tax.getRank() ) && ForesterUtil.isEmpty( tax.getRank() ) ) {
 470             try {
 471                 tax.setRank( up_tax.getRank().toLowerCase() );
 472             }
 473             catch ( final PhyloXmlDataFormatException ex ) {
 474                 tax.setRank( "" );
 475             }
 476         }
 477         if ( ( qt != QUERY_TYPE.ID ) && !ForesterUtil.isEmpty( up_tax.getId() ) && ( tax.getIdentifier() == null ) ) {
 478             tax.setIdentifier( new Identifier( up_tax.getId(), "uniprot" ) );
 479         }
 480         if ( up_tax.getLineage() != null ) {
 481             tax.setLineage( new ArrayList<String>() );
 482             for( final String lin : up_tax.getLineage() ) {
 483                 if ( !ForesterUtil.isEmpty( lin ) ) {
 484                     tax.getLineage().add( lin );
 485                 }
 486             }
 487         }
 488     }
 489
 490     private enum QUERY_TYPE {
 491         CODE, SN, CN, ID;
 492     }
 493 }