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