src/jalview/analysis/Finder.java

   1 /*
   2  * Jalview - A Sequence Alignment Editor and Viewer ($$Version-Rel$$)
   3  * Copyright (C) $$Year-Rel$$ The Jalview Authors
   4  *
   5  * This file is part of Jalview.
   6  *
   7  * Jalview is free software: you can redistribute it and/or
   8  * modify it under the terms of the GNU General Public License
   9  * as published by the Free Software Foundation, either version 3
  10  * of the License, or (at your option) any later version.
  11  *
  12  * Jalview is distributed in the hope that it will be useful, but
  13  * WITHOUT ANY WARRANTY; without even the implied warranty
  14  * of MERCHANTABILITY or FITNESS FOR A PARTICULAR
  15  * PURPOSE.  See the GNU General Public License for more details.
  16  *
  17  * You should have received a copy of the GNU General Public License
  18  * along with Jalview.  If not, see <http://www.gnu.org/licenses/>.
  19  * The Jalview Authors are detailed in the 'AUTHORS' file.
  20  */
  21 package jalview.analysis;
  22
  23 import java.util.ArrayList;
  24 import java.util.Arrays;
  25 import java.util.Iterator;
  26 import java.util.List;
  27 import java.util.Locale;
  28
  29 import com.stevesoft.pat.Regex;
  30
  31 import jalview.api.AlignViewportI;
  32 import jalview.api.FeatureRenderer;
  33 import jalview.api.FinderI;
  34 import jalview.datamodel.AlignmentI;
  35 import jalview.datamodel.SearchResultMatchI;
  36 import jalview.datamodel.SearchResults;
  37 import jalview.datamodel.SearchResultsI;
  38 import jalview.datamodel.SequenceFeature;
  39 import jalview.datamodel.SequenceGroup;
  40 import jalview.datamodel.SequenceI;
  41 import jalview.datamodel.features.SequenceFeaturesI;
  42 import jalview.util.Comparison;
  43 import jalview.util.MapList;
  44
  45 /**
  46  * Implements the search algorithm for the Find dialog
  47  */
  48 public class Finder implements FinderI
  49 {
  50   /*
  51    * matched residue locations
  52    */
  53   private SearchResultsI searchResults;
  54
  55   /*
  56    * sequences matched by id or description
  57    */
  58   private List<SequenceI> idMatches;
  59
  60   /*
  61    * the viewport to search over
  62    */
  63   private AlignViewportI viewport;
  64
  65   /*
  66    * feature renderer model - if available
  67    */
  68   FeatureRenderer frm = null;
  69
  70   /*
  71    * sequence index in alignment to search from
  72    */
  73   private int sequenceIndex;
  74
  75   /*
  76    * position offset in sequence to search from, base 0
  77    * (position after start of last match for a 'find next')
  78    */
  79   private int residueIndex;
  80
  81   /*
  82    * last feature matched when incrementally searching sequence features
  83    */
  84   private SequenceFeature lastFeature;
  85
  86   /*
  87    * last sequenceIndex used when lastFeature was discovered
  88    */
  89   private int lastFeatureSequenceIndex;
  90
  91   /*
  92    * the true sequence position of the start of the
  93    * last sequence searched (when 'ignore hidden regions' does not apply)
  94    */
  95   private int searchedSequenceStartPosition;
  96
  97   /*
  98    * when 'ignore hidden regions' applies, this holds the mapping from
  99    * the visible sequence positions (1, 2, ...) to true sequence positions
 100    */
 101   private MapList searchedSequenceMap;
 102
 103   private String seqToSearch;
 104
 105   /**
 106    * Constructor for searching a viewport
 107    *
 108    * @param av
 109    */
 110   public Finder(AlignViewportI av)
 111   {
 112     this.viewport = av;
 113     this.sequenceIndex = 0;
 114     this.residueIndex = -1;
 115   }
 116
 117   @Override
 118   public void findAll(String theSearchString, boolean matchCase,
 119           boolean searchDescription, boolean searchFeatureDesc,
 120           boolean ignoreHidden)
 121   {
 122     /*
 123      * search from the start
 124      */
 125     lastFeature = null;
 126     lastFeatureSequenceIndex = 0;
 127     sequenceIndex = 0;
 128     residueIndex = -1;
 129
 130     doFind(theSearchString, matchCase, searchDescription, searchFeatureDesc,
 131             true, ignoreHidden);
 132
 133     /*
 134      * reset to start for next search
 135      */
 136     sequenceIndex = 0;
 137     residueIndex = -1;
 138     lastFeature = null;
 139     lastFeatureSequenceIndex = 0;
 140   }
 141
 142   @Override
 143   public void findNext(String theSearchString, boolean matchCase,
 144           boolean searchDescription, boolean searchFeatureDesc,
 145           boolean ignoreHidden)
 146   {
 147     doFind(theSearchString, matchCase, searchDescription, searchFeatureDesc,
 148             false, ignoreHidden);
 149
 150     if (searchResults.isEmpty() && idMatches.isEmpty())
 151     {
 152       /*
 153        * search failed - reset to start for next search
 154        */
 155       sequenceIndex = 0;
 156       residueIndex = -1;
 157       lastFeature = null;
 158       lastFeatureSequenceIndex = 0;
 159     }
 160   }
 161
 162   /**
 163    * Performs a 'find next' or 'find all'
 164    *
 165    * @param theSearchString
 166    * @param matchCase
 167    * @param searchDescription
 168    * @param findAll
 169    * @param ignoreHidden
 170    */
 171   protected void doFind(String theSearchString, boolean matchCase,
 172           boolean searchDescription, boolean searchFeatureDesc,
 173           boolean findAll, boolean ignoreHidden)
 174   {
 175     searchResults = new SearchResults();
 176     idMatches = new ArrayList<>();
 177
 178     String searchString = matchCase ? theSearchString
 179             : theSearchString.toUpperCase(Locale.ROOT);
 180     Regex searchPattern = new Regex(searchString);
 181     searchPattern.setIgnoreCase(!matchCase);
 182
 183     SequenceGroup selection = viewport.getSelectionGroup();
 184     if (selection != null && selection.getSize() < 1)
 185     {
 186       selection = null; // ? ignore column-only selection
 187     }
 188
 189     AlignmentI alignment = viewport.getAlignment();
 190     int end = alignment.getHeight();
 191
 192     getSequence(ignoreHidden);
 193
 194     boolean found = false;
 195     while ((!found || findAll) && sequenceIndex < end)
 196     {
 197       found = findNextMatch(searchString, searchPattern, searchDescription,
 198               searchFeatureDesc, ignoreHidden);
 199     }
 200   }
 201
 202   /**
 203    * Calculates and saves the sequence string to search. The string is
 204    * restricted to the current selection region if there is one, and is saved
 205    * with all gaps removed.
 206    * <p>
 207    * If there are hidden columns, and option {@ignoreHidden} is selected, then
 208    * only visible positions of the sequence are included, and a mapping is also
 209    * constructed from the returned string positions to the true sequence
 210    * positions.
 211    * <p>
 212    * Note we have to do this each time {@code findNext} or {@code findAll} is
 213    * called, in case the alignment, selection group or hidden columns have
 214    * changed. In particular, if the sequence at offset {@code sequenceIndex} in
 215    * the alignment is (no longer) in the selection group, search is advanced to
 216    * the next sequence that is.
 217    * <p>
 218    * Sets sequence string to the empty string if there are no more sequences (in
 219    * selection group if any) at or after {@code sequenceIndex}.
 220    * <p>
 221    * Returns true if a sequence could be found, false if end of alignment was
 222    * reached
 223    *
 224    * @param ignoreHidden
 225    * @return
 226    */
 227   private boolean getSequence(boolean ignoreHidden)
 228   {
 229     AlignmentI alignment = viewport.getAlignment();
 230     if (sequenceIndex >= alignment.getHeight())
 231     {
 232       seqToSearch = "";
 233       return false;
 234     }
 235     SequenceI seq = alignment.getSequenceAt(sequenceIndex);
 236     SequenceGroup selection = viewport.getSelectionGroup();
 237     if (selection != null && !selection.contains(seq))
 238     {
 239       if (!nextSequence(ignoreHidden))
 240       {
 241         return false;
 242       }
 243       seq = alignment.getSequenceAt(sequenceIndex);
 244     }
 245
 246     String seqString = null;
 247     if (ignoreHidden)
 248     {
 249       seqString = getVisibleSequence(seq);
 250       this.searchedSequenceStartPosition = 1;
 251     }
 252     else
 253     {
 254       int startCol = 0;
 255       int endCol = seq.getLength() - 1;
 256       this.searchedSequenceStartPosition = seq.getStart();
 257       if (selection != null)
 258       {
 259         startCol = selection.getStartRes();
 260         endCol = Math.min(endCol, selection.getEndRes());
 261         this.searchedSequenceStartPosition = seq.findPosition(startCol);
 262       }
 263       seqString = seq.getSequenceAsString(startCol, endCol + 1);
 264     }
 265
 266     /*
 267      * remove gaps; note that even if this leaves an empty string, we 'search'
 268      * the sequence anyway (for possible match on name or description)
 269      */
 270     String ungapped = AlignSeq.extractGaps(Comparison.GapChars, seqString);
 271     this.seqToSearch = ungapped;
 272
 273     return true;
 274   }
 275
 276   /**
 277    * Returns a string consisting of only the visible residues of {@code seq}
 278    * from alignment column {@ fromColumn}, restricted to the current selection
 279    * region if there is one.
 280    * <p>
 281    * As a side-effect, also computes the mapping from the true sequence
 282    * positions to the positions (1, 2, ...) of the returned sequence. This is to
 283    * allow search matches in the visible sequence to be converted to sequence
 284    * positions.
 285    *
 286    * @param seq
 287    * @return
 288    */
 289   private String getVisibleSequence(SequenceI seq)
 290   {
 291     /*
 292      * get start / end columns of sequence and convert to base 0
 293      * (so as to match the visible column ranges)
 294      */
 295     int seqStartCol = seq.findIndex(seq.getStart()) - 1;
 296     int seqEndCol = seq.findIndex(seq.getStart() + seq.getLength() - 1) - 1;
 297     Iterator<int[]> visibleColumns = viewport.getViewAsVisibleContigs(true);
 298     StringBuilder visibleSeq = new StringBuilder(seqEndCol - seqStartCol);
 299     List<int[]> fromRanges = new ArrayList<>();
 300
 301     while (visibleColumns.hasNext())
 302     {
 303       int[] range = visibleColumns.next();
 304       if (range[0] > seqEndCol)
 305       {
 306         // beyond the end of the sequence
 307         break;
 308       }
 309       if (range[1] < seqStartCol)
 310       {
 311         // before the start of the sequence
 312         continue;
 313       }
 314       String subseq = seq.getSequenceAsString(range[0], range[1] + 1);
 315       String ungapped = AlignSeq.extractGaps(Comparison.GapChars, subseq);
 316       visibleSeq.append(ungapped);
 317       if (!ungapped.isEmpty())
 318       {
 319         /*
 320          * visible region includes at least one non-gap character,
 321          * so add the range to the mapping being constructed
 322          */
 323         int seqResFrom = seq.findPosition(range[0]);
 324         int seqResTo = seqResFrom + ungapped.length() - 1;
 325         fromRanges.add(new int[] { seqResFrom, seqResTo });
 326       }
 327     }
 328
 329     /*
 330      * construct the mapping
 331      * from: visible sequence positions 1..length
 332      * to:   true residue positions of the alignment sequence
 333      */
 334     List<int[]> toRange = Arrays
 335             .asList(new int[]
 336             { 1, visibleSeq.length() });
 337     searchedSequenceMap = new MapList(fromRanges, toRange, 1, 1);
 338
 339     return visibleSeq.toString();
 340   }
 341
 342   /**
 343    * Advances the search to the next sequence in the alignment. Sequences not in
 344    * the current selection group (if there is one) are skipped. The
 345    * (sub-)sequence to be searched is extracted, gaps removed, and saved, or set
 346    * to null if there are no more sequences to search.
 347    * <p>
 348    * Returns true if a sequence could be found, false if end of alignment was
 349    * reached
 350    *
 351    * @param ignoreHidden
 352    */
 353   private boolean nextSequence(boolean ignoreHidden)
 354   {
 355     sequenceIndex++;
 356     residueIndex = -1;
 357
 358     return getSequence(ignoreHidden);
 359   }
 360
 361   /**
 362    * Finds the next match in the given sequence, starting at offset
 363    * {@code residueIndex}. Answers true if a match is found, else false.
 364    * <p>
 365    * If a match is found, {@code residueIndex} is advanced to the position after
 366    * the start of the matched region, ready for the next search.
 367    * <p>
 368    * If no match is found, {@code sequenceIndex} is advanced ready to search the
 369    * next sequence.
 370    *
 371    * @param seqToSearch
 372    * @param searchString
 373    * @param searchPattern
 374    * @param matchDescription
 375    * @param ignoreHidden
 376    * @return
 377    */
 378   protected boolean findNextMatch(String searchString, Regex searchPattern,
 379           boolean matchDescription, boolean matchFeatureDesc,
 380           boolean ignoreHidden)
 381   {
 382     if (residueIndex < 0)
 383     {
 384       /*
 385        * at start of sequence; try find by residue number, in sequence id,
 386        * or (optionally) in sequence description
 387        */
 388       if (doNonMotifSearches(searchString, searchPattern, matchDescription))
 389       {
 390         return true;
 391       }
 392     }
 393
 394     /*
 395      * search for next match in sequence string
 396      */
 397     int end = seqToSearch.length();
 398     while (residueIndex < end)
 399     {
 400       boolean matched = searchPattern.searchFrom(seqToSearch, residueIndex);
 401       if (matched)
 402       {
 403         if (recordMatch(searchPattern, ignoreHidden))
 404         {
 405           return true;
 406         }
 407       }
 408       else
 409       {
 410         if (matchFeatureDesc)
 411         {
 412           matched = searchSequenceFeatures(residueIndex, searchPattern);
 413           if (matched)
 414           {
 415             return true;
 416           }
 417           lastFeature = null;
 418         }
 419         residueIndex = Integer.MAX_VALUE;
 420       }
 421     }
 422
 423     nextSequence(ignoreHidden);
 424     return false;
 425   }
 426
 427   /**
 428    * Adds the match held in the <code>searchPattern</code> Regex to the
 429    * <code>searchResults</code>, unless it is a subregion of the last match
 430    * recorded. <code>residueIndex</code> is advanced to the position after the
 431    * start of the matched region, ready for the next search. Answers true if a
 432    * match was added, else false.
 433    * <p>
 434    * Matches that lie entirely within hidden regions of the alignment are not
 435    * added.
 436    *
 437    * @param searchPattern
 438    * @param ignoreHidden
 439    * @return
 440    */
 441   protected boolean recordMatch(Regex searchPattern, boolean ignoreHidden)
 442   {
 443     SequenceI seq = viewport.getAlignment().getSequenceAt(sequenceIndex);
 444
 445     /*
 446      * convert start/end of the match to sequence coordinates
 447      */
 448     int offset = searchPattern.matchedFrom();
 449     int matchStartPosition = this.searchedSequenceStartPosition + offset;
 450     int matchEndPosition = matchStartPosition + searchPattern.charsMatched()
 451             - 1;
 452
 453     /*
 454      * update residueIndex to next position after the start of the match
 455      * (findIndex returns a value base 1, columnIndex is held base 0)
 456      */
 457     residueIndex = searchPattern.matchedFrom() + 1;
 458
 459     /*
 460      * return false if the match is entirely in a hidden region
 461      */
 462     if (allHidden(seq, matchStartPosition, matchEndPosition))
 463     {
 464       return false;
 465     }
 466
 467     /*
 468      * check that this match is not a subset of the previous one (JAL-2302)
 469      */
 470     List<SearchResultMatchI> matches = searchResults.getResults();
 471     SearchResultMatchI lastMatch = matches.isEmpty() ? null
 472             : matches.get(matches.size() - 1);
 473
 474     if (lastMatch == null || !lastMatch.contains(seq, matchStartPosition,
 475             matchEndPosition))
 476     {
 477       addMatch(seq, matchStartPosition, matchEndPosition, ignoreHidden);
 478       return true;
 479     }
 480
 481     return false;
 482   }
 483
 484   /**
 485    * Adds one match to the stored list. If hidden residues are being skipped,
 486    * then the match may need to be split into contiguous positions of the
 487    * sequence (so it does not include skipped residues).
 488    *
 489    * @param seq
 490    * @param matchStartPosition
 491    * @param matchEndPosition
 492    * @param ignoreHidden
 493    */
 494   private void addMatch(SequenceI seq, int matchStartPosition,
 495           int matchEndPosition, boolean ignoreHidden)
 496   {
 497     if (!ignoreHidden)
 498     {
 499       /*
 500        * simple case
 501        */
 502       searchResults.addResult(seq, matchStartPosition, matchEndPosition);
 503       return;
 504     }
 505
 506     /*
 507      *  get start-end contiguous ranges in underlying sequence
 508      */
 509     int[] truePositions = searchedSequenceMap
 510             .locateInFrom(matchStartPosition, matchEndPosition);
 511     searchResults.addResult(seq, truePositions);
 512   }
 513
 514   /**
 515    * Returns true if all residues are hidden, else false
 516    *
 517    * @param seq
 518    * @param fromPos
 519    * @param toPos
 520    * @return
 521    */
 522   private boolean allHidden(SequenceI seq, int fromPos, int toPos)
 523   {
 524     if (!viewport.hasHiddenColumns())
 525     {
 526       return false;
 527     }
 528     for (int res = fromPos; res <= toPos; res++)
 529     {
 530       if (isVisible(seq, res))
 531       {
 532         return false;
 533       }
 534     }
 535     return true;
 536   }
 537
 538   /**
 539    * Does searches other than for residue patterns. Currently this includes
 540    * <ul>
 541    * <li>find residue by position (if search string is a number)</li>
 542    * <li>match search string to sequence id</li>
 543    * <li>match search string to sequence description (optional)</li>
 544    * </ul>
 545    * Answers true if a match is found, else false.
 546    *
 547    * @param searchString
 548    * @param searchPattern
 549    * @param includeDescription
 550    * @return
 551    */
 552   protected boolean doNonMotifSearches(String searchString,
 553           Regex searchPattern, boolean includeDescription)
 554   {
 555     SequenceI seq = viewport.getAlignment().getSequenceAt(sequenceIndex);
 556
 557     /*
 558      * position sequence search to start of sequence
 559      */
 560     residueIndex = 0;
 561     try
 562     {
 563       int res = Integer.parseInt(searchString);
 564       return searchForResidueNumber(seq, res);
 565     } catch (NumberFormatException ex)
 566     {
 567       // search pattern is not a number
 568     }
 569
 570     if (searchSequenceName(seq, searchPattern))
 571     {
 572       return true;
 573     }
 574     if (includeDescription && searchSequenceDescription(seq, searchPattern))
 575     {
 576       return true;
 577     }
 578     return false;
 579   }
 580
 581   /**
 582    * Searches for a match with the sequence features, and if found, adds the
 583    * sequence to the list of match ids, (but not as a duplicate). Answers true
 584    * if a match was added, else false.
 585    *
 586    * @param seq
 587    * @param searchPattern
 588    * @return
 589    */
 590   protected boolean searchSequenceFeatures(int from, Regex searchPattern)
 591   {
 592     if (lastFeatureSequenceIndex != sequenceIndex)
 593     {
 594       lastFeatureSequenceIndex = sequenceIndex;
 595       lastFeature = null;
 596     }
 597     SequenceI seq = viewport.getAlignment().getSequenceAt(sequenceIndex);
 598     SequenceFeaturesI sf = seq.getFeatures();
 599
 600     // TODO - stash feature list and search incrementally
 601     List<SequenceFeature> allFeatures = null;
 602     if (frm != null)
 603     {
 604       allFeatures = frm.findFeaturesAtResidue(seq, seq.getStart(),
 605               seq.getEnd());
 606     }
 607     else
 608     {
 609       allFeatures = sf.getAllFeatures(null);
 610     }
 611     // so we can check we are advancing when debugging
 612     long fpos = 0;
 613
 614     for (SequenceFeature feature : allFeatures)
 615     {
 616       fpos++;
 617       if (lastFeature != null)
 618       {
 619         // iterate till we find last feature matched
 620         if (lastFeature != feature)
 621         {
 622           continue;
 623         }
 624         else
 625         {
 626           lastFeature = null;
 627           continue;
 628         }
 629       }
 630
 631       if (searchPattern.search(feature.type) || (feature.description != null
 632               && searchPattern.search(feature.description)))
 633       {
 634         searchResults.addResult(seq, feature.getBegin(), feature.getEnd());
 635         lastFeature = feature;
 636         return true;
 637       }
 638     }
 639     residueIndex = Integer.MAX_VALUE;
 640     lastFeature = null;
 641     return false;
 642   }
 643
 644   /**
 645    * Searches for a match with the sequence description, and if found, adds the
 646    * sequence to the list of match ids (but not as a duplicate). Answers true if
 647    * a match was added, else false.
 648    *
 649    * @param seq
 650    * @param searchPattern
 651    * @return
 652    */
 653   protected boolean searchSequenceDescription(SequenceI seq,
 654           Regex searchPattern)
 655   {
 656     String desc = seq.getDescription();
 657     if (desc != null && searchPattern.search(desc)
 658             && !idMatches.contains(seq))
 659     {
 660       idMatches.add(seq);
 661       return true;
 662     }
 663     return false;
 664   }
 665
 666   /**
 667    * Searches for a match with the sequence name, and if found, adds the
 668    * sequence to the list of match ids (but not as a duplicate). Answers true if
 669    * a match was added, else false.
 670    *
 671    * @param seq
 672    * @param searchPattern
 673    * @return
 674    */
 675   protected boolean searchSequenceName(SequenceI seq, Regex searchPattern)
 676   {
 677     if (searchPattern.search(seq.getName()) && !idMatches.contains(seq))
 678     {
 679       idMatches.add(seq);
 680       return true;
 681     }
 682     return false;
 683   }
 684
 685   /**
 686    * If the residue position is valid for the sequence, and in a visible column,
 687    * adds the position to the search results and returns true, else answers
 688    * false.
 689    *
 690    * @param seq
 691    * @param resNo
 692    * @return
 693    */
 694   protected boolean searchForResidueNumber(SequenceI seq, int resNo)
 695   {
 696     if (seq.getStart() <= resNo && seq.getEnd() >= resNo)
 697     {
 698       if (isVisible(seq, resNo))
 699       {
 700         searchResults.addResult(seq, resNo, resNo);
 701         return true;
 702       }
 703     }
 704     return false;
 705   }
 706
 707   /**
 708    * Returns true if the residue is in a visible column, else false
 709    *
 710    * @param seq
 711    * @param res
 712    * @return
 713    */
 714   private boolean isVisible(SequenceI seq, int res)
 715   {
 716     if (!viewport.hasHiddenColumns())
 717     {
 718       return true;
 719     }
 720     int col = seq.findIndex(res); // base 1
 721     return viewport.getAlignment().getHiddenColumns().isVisible(col - 1); // base
 722                                                                           // 0
 723   }
 724
 725   @Override
 726   public List<SequenceI> getIdMatches()
 727   {
 728     return idMatches;
 729   }
 730
 731   @Override
 732   public SearchResultsI getSearchResults()
 733   {
 734     return searchResults;
 735   }
 736
 737   @Override
 738   public void setFeatureRenderer(FeatureRenderer featureRenderer)
 739   {
 740     frm = featureRenderer;
 741   }
 742 }