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