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.util.Comparison;
  30
  31 import java.util.Vector;
  32
  33 import com.stevesoft.pat.Regex;
  34
  35 /**
  36  * Implements the search algorithm for the Find dialog
  37  */
  38 public class Finder
  39 {
  40   /*
  41    * match residue locations
  42    */
  43   private SearchResultsI searchResults;
  44
  45   /*
  46    * sequences matched by id or description
  47    */
  48   private Vector<SequenceI> idMatch;
  49
  50   /*
  51    * the alignment to search over
  52    */
  53   private AlignmentI alignment;
  54
  55   /*
  56    * (optional) selection to restrict search to
  57    */
  58   private SequenceGroup selection;
  59
  60   /*
  61    * set true for case-sensitive search (default is false)
  62    */
  63   private boolean caseSensitive;
  64
  65   /*
  66    * set true to search sequence description (default is false)
  67    */
  68   private boolean includeDescription;
  69
  70   /*
  71    * set true to return all matches (default is next match only)
  72    */
  73   private boolean findAll;
  74
  75   /*
  76    * sequence index in alignment to search from
  77    */
  78   private int seqIndex;
  79
  80   /*
  81    * residue position in sequence to search from, base 1
  82    * (position of last match for a repeat search)
  83    */
  84   private int resIndex;
  85
  86   /**
  87    * Constructor to start searching an alignment, optionally restricting results
  88    * to a selection
  89    *
  90    * @param al
  91    * @param sel
  92    */
  93   public Finder(AlignmentI al, SequenceGroup sel)
  94   {
  95     this(al, sel, 0, -1);
  96   }
  97
  98   /**
  99    * Constructor to resume search at given sequence and residue on alignment and
 100    * (optionally) restricted to a selection
 101    *
 102    * @param al
 103    * @param sel
 104    * @param seqindex
 105    * @param resindex
 106    */
 107   public Finder(AlignmentI al, SequenceGroup sel, int seqindex,
 108           int resindex)
 109   {
 110     this.alignment = al;
 111     this.selection = sel;
 112     this.seqIndex = seqindex;
 113     this.resIndex = resindex;
 114   }
 115
 116   /**
 117    * Performs a find for the given search string. By default the next match is
 118    * found, but if setFindAll(true) has been called, then all matches are found.
 119    * Sequences matched by id or description can be retrieved by getIdMatch(),
 120    * and matched residue patterns by getSearchResults().
 121    *
 122    * @param theSearchString
 123    * @return
 124    */
 125   public void find(String theSearchString)
 126   {
 127     String searchString = caseSensitive ? theSearchString.toUpperCase()
 128             : theSearchString;
 129     Regex regex = new Regex(searchString);
 130     regex.setIgnoreCase(!caseSensitive);
 131     searchResults = new SearchResults();
 132     idMatch = new Vector<>();
 133
 134     if (selection != null && selection.getSize() < 1)
 135     {
 136       selection = null; // ? ignore column-only selection
 137     }
 138
 139     boolean finished = false;
 140     int end = alignment.getHeight();
 141
 142     while (!finished && (seqIndex < end))
 143     {
 144       SequenceI seq = alignment.getSequenceAt(seqIndex);
 145
 146       if ((selection != null) && !selection.contains(seq))
 147       {
 148         // this sequence is not in the selection - skip to next sequence
 149         seqIndex++;
 150         resIndex = -1;
 151         continue;
 152       }
 153
 154       if (resIndex < 0)
 155       {
 156         /*
 157          * at start of sequence; try find by residue number, in sequence id,
 158          * or (optionally) in sequence description
 159          */
 160         resIndex = 0;
 161         if (doNonMotifSearches(seq, searchString, regex))
 162         {
 163           return;
 164         }
 165       }
 166
 167       finished = searchSequenceString(seq, regex) && !findAll;
 168
 169       if (!finished)
 170       {
 171         seqIndex++;
 172         resIndex = -1;
 173       }
 174     }
 175   }
 176
 177   /**
 178    * Searches the sequence, starting from <code>resIndex</code> (base 1), and
 179    * adds matches to <code>searchResults</code>. The search is restricted to the
 180    * <code>selection</code> region if there is one. Answers true if any match is
 181    * added, else false.
 182    *
 183    * @param seq
 184    * @param regex
 185    * @return
 186    */
 187   protected boolean searchSequenceString(SequenceI seq, Regex regex)
 188   {
 189     /*
 190      * Restrict search to selected region if there is one
 191      */
 192     int seqColStart = 0;
 193     int seqColEnd = seq.getLength() - 1;
 194     int residueOffset = 0;
 195     if (selection != null)
 196     {
 197       int selColEnd = selection.getEndRes();
 198       int selColStart = selection.getStartRes();
 199       if (selColStart > seqColEnd)
 200       {
 201         return false; // sequence doesn't reach selection region
 202       }
 203       seqColStart = selColStart;
 204       seqColEnd = Math.min(seqColEnd, selColEnd);
 205       residueOffset = seq.findPosition(selection.getStartRes())
 206               - seq.getStart();
 207     }
 208     String seqString = seq.getSequenceAsString(seqColStart, seqColEnd + 1);
 209
 210     String noGaps = AlignSeq.extractGaps(Comparison.GapChars, seqString);
 211
 212     SearchResultMatchI lastMatch = null;
 213     boolean found = false;
 214
 215     for (int r = resIndex; r < noGaps.length(); r++)
 216     {
 217       /*
 218        * searchFrom position is base 0, r is base 1,
 219        * so search is from the position after the r'th residue
 220        */
 221       if (regex.searchFrom(noGaps, r))
 222       {
 223         resIndex = regex.matchedFrom();
 224         resIndex += residueOffset; // add back #residues before selection region
 225         int matchStartPosition = resIndex + seq.getStart();
 226         int matchEndPosition = matchStartPosition + regex.charsMatched()
 227                 - 1;
 228         if (lastMatch == null || !lastMatch.contains(seq,
 229                 matchStartPosition, matchEndPosition))
 230         {
 231           lastMatch = searchResults.addResult(seq, matchStartPosition,
 232                   matchEndPosition);
 233           found = true;
 234         }
 235         if (!findAll)
 236         {
 237           resIndex++;
 238           return true;
 239         }
 240         r = resIndex;
 241       }
 242       else
 243       {
 244         break;
 245       }
 246     }
 247     return found;
 248   }
 249
 250   /**
 251    * Does searches other than for residue patterns. Currently this includes
 252    * <ul>
 253    * <li>find residue by position (if search string is a number)</li>
 254    * <li>match search string to sequence id</li>
 255    * <li>match search string to sequence description (optional)</li>
 256    * </ul>
 257    * Answers true if a match is found and we are not doing 'find all' (so this
 258    * search action is complete), else false.
 259    *
 260    * @param seq
 261    * @param searchString
 262    * @param regex
 263    * @return
 264    */
 265   protected boolean doNonMotifSearches(SequenceI seq, String searchString,
 266           Regex regex)
 267   {
 268     if (searchForResidueNumber(seq, searchString) && !findAll)
 269     {
 270       return true;
 271     }
 272     if (searchSequenceName(seq, regex) && !findAll)
 273     {
 274       return true;
 275     }
 276     if (searchSequenceDescription(seq, regex) && !findAll)
 277     {
 278       return true;
 279     }
 280     return false;
 281   }
 282
 283   /**
 284    * Searches for a match with the sequence description, if that option was
 285    * requested, and if found, adds the sequence to the list of match ids (but
 286    * not as a duplicate). Answers true if a match was added, else false.
 287    *
 288    * @param seq
 289    * @param regex
 290    * @return
 291    */
 292   protected boolean searchSequenceDescription(SequenceI seq, Regex regex)
 293   {
 294     if (!includeDescription)
 295     {
 296       return false;
 297     }
 298     String desc = seq.getDescription();
 299     if (desc != null && regex.search(desc) && !idMatch.contains(seq))
 300     {
 301       idMatch.addElement(seq);
 302       return true;
 303     }
 304     return false;
 305   }
 306
 307   /**
 308    * Searches for a match with the sequence name, and if found, adds the
 309    * sequence to the list of match ids (but not as a duplicate). Answers true if
 310    * a match was added, else false.
 311    *
 312    * @param seq
 313    * @param regex
 314    * @return
 315    */
 316   protected boolean searchSequenceName(SequenceI seq, Regex regex)
 317   {
 318     if (regex.search(seq.getName()) && !idMatch.contains(seq))
 319     {
 320       idMatch.addElement(seq);
 321       return true;
 322     }
 323     return false;
 324   }
 325
 326   /**
 327    * Tries to interpret the search string as a residue position, and if valid,
 328    * adds the position to the search results
 329    */
 330   protected boolean searchForResidueNumber(SequenceI seq, String searchString)
 331   {
 332     try
 333     {
 334       int res = Integer.parseInt(searchString);
 335       if (seq.getStart() <= res && seq.getEnd() >= res)
 336       {
 337         searchResults.addResult(seq, res, res);
 338         return true;
 339       }
 340     } catch (NumberFormatException ex)
 341     {
 342     }
 343     return false;
 344   }
 345
 346   /**
 347    * Sets whether the search is case sensitive (default is no)
 348    *
 349    * @param value
 350    */
 351   public void setCaseSensitive(boolean value)
 352   {
 353     this.caseSensitive = value;
 354   }
 355
 356   /**
 357    * Sets whether search returns all matches. Default is to return the next
 358    * match only.
 359    *
 360    * @param value
 361    */
 362   public void setFindAll(boolean value)
 363   {
 364     this.findAll = value;
 365   }
 366
 367   /**
 368    * Returns the (possibly empty) list of matching sequences (when search
 369    * includes searching sequence names)
 370    *
 371    * @return
 372    */
 373   public Vector<SequenceI> getIdMatch()
 374   {
 375     return idMatch;
 376   }
 377
 378   /**
 379    * @return the searchResults
 380    */
 381   public SearchResultsI getSearchResults()
 382   {
 383     return searchResults;
 384   }
 385
 386   /**
 387    * @return the resIndex
 388    */
 389   public int getResIndex()
 390   {
 391     return resIndex;
 392   }
 393
 394   /**
 395    * @return the seqIndex
 396    */
 397   public int getSeqIndex()
 398   {
 399     return seqIndex;
 400   }
 401
 402   /**
 403    * Sets whether search also searches in sequence description text (default is
 404    * no)
 405    *
 406    * @param value
 407    */
 408   public void setIncludeDescription(boolean value)
 409   {
 410     this.includeDescription = value;
 411   }
 412 }