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