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