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 jalview.datamodel.AlignmentI;
  24 import jalview.datamodel.Range;
  25 import jalview.datamodel.SearchResultMatchI;
  26 import jalview.datamodel.SearchResults;
  27 import jalview.datamodel.SearchResultsI;
  28 import jalview.datamodel.SequenceGroup;
  29 import jalview.datamodel.SequenceI;
  30 import jalview.datamodel.VisibleContigsIterator;
  31 import jalview.util.Comparison;
  32
  33 import java.util.List;
  34 import java.util.Vector;
  35
  36 import com.stevesoft.pat.Regex;
  37
  38 /**
  39  * Implements the search algorithm for the Find dialog
  40  */
  41 public class Finder
  42 {
  43   /*
  44    * matched residue locations
  45    */
  46   private SearchResultsI searchResults;
  47
  48   /*
  49    * sequences matched by id or description
  50    */
  51   private Vector<SequenceI> idMatch;
  52
  53   /*
  54    * the alignment to search over
  55    */
  56   private AlignmentI alignment;
  57
  58   /*
  59    * (optional) selection to restrict search to
  60    */
  61   private SequenceGroup selection;
  62
  63   /*
  64    * set true for case-sensitive search (default is false)
  65    */
  66   private boolean caseSensitive;
  67
  68   /*
  69    * set true to search sequence description (default is false)
  70    */
  71   private boolean includeDescription;
  72
  73   /*
  74    * set true to return all matches (default is next match only)
  75    */
  76   private boolean findAll;
  77
  78   /*
  79    * sequence index in alignment to search from
  80    */
  81   private int sequenceIndex;
  82
  83   /*
  84    * column position in sequence to search from, base 0
  85    * - absolute column number including any hidden columns
  86    * (position of last match for a repeat search)
  87    */
  88   private int columnIndex;
  89
  90   /**
  91    * Constructor to start searching an alignment, optionally restricting results
  92    * to a selection
  93    *
  94    * @param al
  95    * @param sel
  96    */
  97   public Finder(AlignmentI al, SequenceGroup sel)
  98   {
  99     this(al, sel, 0, -1);
 100   }
 101
 102   /**
 103    * Constructor to resume search at given sequence and residue on alignment and
 104    * (optionally) restricted to a selection
 105    *
 106    * @param al
 107    * @param sel
 108    * @param seqindex
 109    * @param colindex
 110    */
 111   public Finder(AlignmentI al, SequenceGroup sel, int seqindex,
 112           int colindex)
 113   {
 114     this.alignment = al;
 115     this.selection = sel;
 116     this.sequenceIndex = seqindex;
 117     this.columnIndex = colindex;
 118   }
 119
 120   /**
 121    * Performs a find for the given search string. By default the next match is
 122    * found, but if setFindAll(true) has been called, then all matches are found.
 123    * Sequences matched by id or description can be retrieved by getIdMatch(),
 124    * and matched residue patterns by getSearchResults().
 125    *
 126    * @param theSearchString
 127    * @return
 128    */
 129   public void find(String theSearchString)
 130   {
 131     if (findAll)
 132     {
 133       sequenceIndex = 0;
 134       columnIndex = -1;
 135     }
 136
 137     String searchString = caseSensitive ? theSearchString
 138             : theSearchString.toUpperCase();
 139     Regex searchPattern = new Regex(searchString);
 140     searchPattern.setIgnoreCase(!caseSensitive);
 141     searchResults = new SearchResults();
 142     idMatch = new Vector<>();
 143
 144     if (selection != null && selection.getSize() < 1)
 145     {
 146       selection = null; // ? ignore column-only selection
 147     }
 148
 149     int end = alignment.getHeight();
 150
 151     while (sequenceIndex < end)
 152     {
 153       SequenceI seq = alignment.getSequenceAt(sequenceIndex);
 154       boolean found = findNext(seq, searchString, searchPattern);
 155       if (found && !findAll)
 156       {
 157         return;
 158       }
 159       if (!found)
 160       {
 161         sequenceIndex++;
 162         columnIndex = -1;
 163       }
 164     }
 165   }
 166
 167   /**
 168    * Answers the start-end column range of the visible region of
 169    * <code>sequence</code> starting at or after the given <code>column</code>.
 170    * If there are no hidden columns, this just returns the remaining width of
 171    * the sequence. The range is restricted to the current <code>selection</code>
 172    * if there is one. Answers null if there are no visible columns at or after
 173    * <code>column</code>.
 174    */
 175   protected Range getNextVisibleSequenceRegion(SequenceI sequence,
 176           int column)
 177   {
 178     int seqColStart = column;
 179     int seqColEnd = sequence.getLength() - 1;
 180
 181     /*
 182      * restrict search to (next) visible column region,
 183      * in case there are hidden columns
 184      */
 185     VisibleContigsIterator visibleRegions = alignment.getHiddenColumns()
 186             .getVisContigsIterator(column, alignment.getWidth(),
 187                     false);
 188     int[] visible = visibleRegions.hasNext() ? visibleRegions.next() : null;
 189     if (visible == null)
 190     {
 191       columnIndex = seqColEnd + 1;
 192       return null;
 193     }
 194     seqColStart = Math.max(seqColStart, visible[0]);
 195     seqColEnd = Math.min(seqColEnd, visible[1]);
 196
 197     /*
 198      * restrict search to selected region if there is one
 199      */
 200     if (selection != null)
 201     {
 202       int selectionStart = selection.getStartRes();
 203       int selectionEnd = selection.getEndRes();
 204       if (selectionStart > seqColEnd || selectionEnd < seqColStart)
 205       {
 206         /*
 207          * sequence region doesn't overlap selection region
 208          */
 209         columnIndex = seqColEnd + 1;
 210         return null;
 211       }
 212       seqColStart = Math.max(seqColStart, selectionStart);
 213       seqColEnd = Math.min(seqColEnd, selectionEnd);
 214     }
 215
 216     return new Range(seqColStart, seqColEnd);
 217   }
 218
 219   /**
 220    * Finds the next match in the given sequence, starting at column at
 221    * <code>columnIndex</code>. Answers true if a match is found, else false. If
 222    * a match is found, <code>columnIndex</code> is advanced to the column after
 223    * the start of the matched region, ready for a search from the next position.
 224    *
 225    * @param seq
 226    * @param searchString
 227    * @param searchPattern
 228    * @return
 229    */
 230   protected boolean findNext(SequenceI seq, String searchString,
 231           Regex searchPattern)
 232   {
 233     if (selection != null && !selection.contains(seq))
 234     {
 235       /*
 236        * this sequence is not in the selection - advance to next sequence
 237        */
 238       return false;
 239     }
 240
 241     if (columnIndex < 0)
 242     {
 243       /*
 244        * at start of sequence; try find by residue number, in sequence id,
 245        * or (optionally) in sequence description
 246        */
 247       if (doNonMotifSearches(seq, searchString, searchPattern))
 248       {
 249         return true;
 250       }
 251     }
 252
 253     /*
 254      * search for next match in sequence string
 255      */
 256     int end = seq.getLength();
 257     while (columnIndex < end)
 258     {
 259       if (searchNextVisibleRegion(seq, searchPattern))
 260       {
 261         return true;
 262       }
 263     }
 264     return false;
 265   }
 266
 267   /**
 268    * Searches the sequence, starting from <code>columnIndex</code>, and adds the
 269    * next match (if any) to <code>searchResults</code>. The search is restricted
 270    * to the next visible column region, and to the <code>selection</code> region
 271    * if there is one. Answers true if a match is added, else false.
 272    *
 273    * @param seq
 274    * @param searchPattern
 275    * @return
 276    */
 277   protected boolean searchNextVisibleRegion(SequenceI seq, Regex searchPattern)
 278   {
 279     Range visible = getNextVisibleSequenceRegion(seq, columnIndex);
 280     if (visible == null)
 281     {
 282       return false;
 283     }
 284     String seqString = seq.getSequenceAsString(visible.start, visible.end + 1);
 285     String noGaps = AlignSeq.extractGaps(Comparison.GapChars, seqString);
 286
 287     if (searchPattern.search(noGaps))
 288     {
 289       int sequenceStartPosition = seq.findPosition(visible.start);
 290       recordMatch(seq, searchPattern, sequenceStartPosition);
 291       return true;
 292     }
 293     else
 294     {
 295       /*
 296        * no match - advance columnIndex past this visible region
 297        * so the next visible region (if any) is searched next
 298        */
 299       columnIndex = visible.end + 1;
 300     }
 301
 302     return false;
 303   }
 304
 305   /**
 306    * Adds the match held in the <code>searchPattern</code> Regex to the
 307    * <code>searchResults</code>, unless it is a subregion of the last match
 308    * recorded. <code>columnIndex</code> is advanced to the position after the
 309    * start of the matched region, ready for the next search. Answers true if a
 310    * match was added, else false.
 311    *
 312    * @param seq
 313    * @param searchPattern
 314    * @param firstResiduePosition
 315    * @return
 316    */
 317   protected boolean recordMatch(SequenceI seq, Regex searchPattern,
 318           int firstResiduePosition)
 319   {
 320     /*
 321      * get start/end of the match in sequence coordinates
 322      */
 323     int offset = searchPattern.matchedFrom();
 324     int matchStartPosition = firstResiduePosition + offset;
 325     int matchEndPosition = matchStartPosition
 326             + searchPattern.charsMatched() - 1;
 327
 328     /*
 329      * update columnIndex to next column after the start of the match
 330      * (findIndex returns a value base 1, columnIndex is held base 0)
 331      */
 332     columnIndex = seq.findIndex(matchStartPosition);
 333
 334     /*
 335      * check that this match is not a subset of the previous one (JAL-2302)
 336      */
 337     List<SearchResultMatchI> matches = searchResults.getResults();
 338     SearchResultMatchI lastMatch = matches.isEmpty() ? null
 339             : matches.get(matches.size() - 1);
 340
 341     if (lastMatch == null || !lastMatch.contains(seq, matchStartPosition,
 342             matchEndPosition))
 343     {
 344       searchResults.addResult(seq, matchStartPosition, matchEndPosition);
 345       return true;
 346     }
 347
 348     return false;
 349   }
 350
 351   /**
 352    * Does searches other than for residue patterns. Currently this includes
 353    * <ul>
 354    * <li>find residue by position (if search string is a number)</li>
 355    * <li>match search string to sequence id</li>
 356    * <li>match search string to sequence description (optional)</li>
 357    * </ul>
 358    * Answers true if a match is found, else false.
 359    *
 360    * @param seq
 361    * @param searchString
 362    * @param searchPattern
 363    * @return
 364    */
 365   protected boolean doNonMotifSearches(SequenceI seq, String searchString,
 366           Regex searchPattern)
 367   {
 368     /*
 369      * position sequence search to start of sequence
 370      */
 371     columnIndex = 0;
 372
 373     if (searchForResidueNumber(seq, searchString))
 374     {
 375       return true;
 376     }
 377     if (searchSequenceName(seq, searchPattern))
 378     {
 379       return true;
 380     }
 381     if (includeDescription && searchSequenceDescription(seq, searchPattern))
 382     {
 383       return true;
 384     }
 385     return false;
 386   }
 387
 388   /**
 389    * Searches for a match with the sequence description, and if found, adds the
 390    * sequence to the list of match ids (but not as a duplicate). Answers true if
 391    * a match was added, else false.
 392    *
 393    * @param seq
 394    * @param searchPattern
 395    * @return
 396    */
 397   protected boolean searchSequenceDescription(SequenceI seq, Regex searchPattern)
 398   {
 399     String desc = seq.getDescription();
 400     if (desc != null && searchPattern.search(desc) && !idMatch.contains(seq))
 401     {
 402       idMatch.addElement(seq);
 403       return true;
 404     }
 405     return false;
 406   }
 407
 408   /**
 409    * Searches for a match with the sequence name, and if found, adds the
 410    * sequence to the list of match ids (but not as a duplicate). Answers true if
 411    * a match was added, else false.
 412    *
 413    * @param seq
 414    * @param searchPattern
 415    * @return
 416    */
 417   protected boolean searchSequenceName(SequenceI seq, Regex searchPattern)
 418   {
 419     if (searchPattern.search(seq.getName()) && !idMatch.contains(seq))
 420     {
 421       idMatch.addElement(seq);
 422       return true;
 423     }
 424     return false;
 425   }
 426
 427   /**
 428    * Tries to interpret the search string as a residue position, and if valid,
 429    * adds the position to the search results and returns true, else answers
 430    * false
 431    */
 432   protected boolean searchForResidueNumber(SequenceI seq, String searchString)
 433   {
 434     try
 435     {
 436       int res = Integer.parseInt(searchString);
 437       if (seq.getStart() <= res && seq.getEnd() >= res)
 438       {
 439         searchResults.addResult(seq, res, res);
 440         return true;
 441       }
 442     } catch (NumberFormatException ex)
 443     {
 444     }
 445     return false;
 446   }
 447
 448   /**
 449    * Sets whether the search is case sensitive (default is no)
 450    *
 451    * @param value
 452    */
 453   public void setCaseSensitive(boolean value)
 454   {
 455     this.caseSensitive = value;
 456   }
 457
 458   /**
 459    * Sets whether search returns all matches. Default is to return the next
 460    * match only.
 461    *
 462    * @param value
 463    */
 464   public void setFindAll(boolean value)
 465   {
 466     this.findAll = value;
 467   }
 468
 469   /**
 470    * Returns the (possibly empty) list of sequences matched on sequence name or
 471    * description
 472    *
 473    * @return
 474    */
 475   public Vector<SequenceI> getIdMatch()
 476   {
 477     return idMatch;
 478   }
 479
 480   /**
 481    * Answers the search results (possibly empty) from the last search
 482    *
 483    * @return
 484    */
 485   public SearchResultsI getSearchResults()
 486   {
 487     return searchResults;
 488   }
 489
 490   /**
 491    * Answers the absolute column position (base 0, including any hidden columns)
 492    * of the start of the last sequence motif (residue pattern) match found. A
 493    * 'Find next' will search from the next position.
 494    *
 495    * @return
 496    */
 497   public int getColumnIndex()
 498   {
 499     return columnIndex;
 500   }
 501
 502   /**
 503    * Answers the offset in the alignment (0..) of the sequence in which the last
 504    * match was found (if any)
 505    *
 506    * @return
 507    */
 508   public int getSequenceIndex()
 509   {
 510     return sequenceIndex;
 511   }
 512
 513   /**
 514    * Sets whether search also searches in sequence description text (default is
 515    * no)
 516    *
 517    * @param value
 518    */
 519   public void setIncludeDescription(boolean value)
 520   {
 521     this.includeDescription = value;
 522   }
 523 }