2 * Jalview - A Sequence Alignment Editor and Viewer ($$Version-Rel$$)
3 * Copyright (C) $$Year-Rel$$ The Jalview Authors
5 * This file is part of Jalview.
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.
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.
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.
21 package jalview.analysis;
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;
32 import java.util.List;
33 import java.util.Vector;
35 import com.stevesoft.pat.Regex;
38 * Implements the search algorithm for the Find dialog
43 * matched residue locations
45 private SearchResultsI searchResults;
48 * sequences matched by id or description
50 private Vector<SequenceI> idMatch;
53 * the alignment to search over
55 private AlignmentI alignment;
58 * (optional) selection to restrict search to
60 private SequenceGroup selection;
63 * set true for case-sensitive search (default is false)
65 private boolean caseSensitive;
68 * set true to search sequence description (default is false)
70 private boolean includeDescription;
73 * set true to return all matches (default is next match only)
75 private boolean findAll;
78 * sequence index in alignment to search from
80 private int sequenceIndex;
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)
87 private int columnIndex;
90 * Constructor to start searching an alignment, optionally restricting results
96 public Finder(AlignmentI al, SequenceGroup sel)
102 * Constructor to resume search at given sequence and residue on alignment and
103 * (optionally) restricted to a selection
110 public Finder(AlignmentI al, SequenceGroup sel, int seqindex,
114 this.selection = sel;
115 this.sequenceIndex = seqindex;
116 this.columnIndex = colindex;
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().
125 * @param theSearchString
128 public void find(String theSearchString)
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<>();
143 if (selection != null && selection.getSize() < 1)
145 selection = null; // ? ignore column-only selection
148 int end = alignment.getHeight();
150 while (sequenceIndex < end)
152 SequenceI seq = alignment.getSequenceAt(sequenceIndex);
153 boolean found = findNext(seq, searchString, searchPattern);
154 if (found && !findAll)
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>.
172 protected int[] getNextVisibleRegion(int column)
174 VisibleContigsIterator visibleRegions = alignment.getHiddenColumns()
175 .getVisContigsIterator(column, alignment.getWidth(),
177 return visibleRegions.hasNext() ? visibleRegions.next() : null;
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.
187 * @param searchString
188 * @param searchPattern
191 protected boolean findNext(SequenceI seq, String searchString,
194 if (selection != null && !selection.contains(seq))
197 * this sequence is not in the selection - advance to next sequence
205 * at start of sequence; try find by residue number, in sequence id,
206 * or (optionally) in sequence description
208 if (doNonMotifSearches(seq, searchString, searchPattern))
215 * search for next match in sequence string
217 int end = seq.getLength();
218 while (columnIndex < end)
220 if (searchNextVisibleRegion(seq, searchPattern))
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.
235 * @param searchPattern
238 protected boolean searchNextVisibleRegion(SequenceI seq, Regex searchPattern)
241 * sequence columns to search (working in absolute column
242 * positions, base 0, including any hidden columns)
244 int seqColStart = columnIndex;
245 int seqColEnd = seq.getLength() - 1;
248 * restrict search to (next) visible column region,
249 * in case there are hidden columns
251 int[] visible = getNextVisibleRegion(columnIndex);
254 seqColStart = Math.max(seqColStart, visible[0]);
255 seqColEnd = Math.min(seqColEnd, visible[1]);
259 columnIndex = seqColEnd + 1;
264 * restrict search to selected region if there is one
266 if (selection != null)
268 int selectionStart = selection.getStartRes();
269 int selectionEnd = selection.getEndRes();
270 if (selectionStart > seqColEnd || selectionEnd < seqColStart)
273 * sequence region doesn't overlap selection region -
274 * no match, advance to next visible region
276 columnIndex = seqColEnd + 1;
279 seqColStart = Math.max(seqColStart, selectionStart);
280 seqColEnd = Math.min(seqColEnd, selectionEnd);
283 String seqString = seq.getSequenceAsString(seqColStart, seqColEnd + 1);
284 String noGaps = AlignSeq.extractGaps(Comparison.GapChars, seqString);
286 if (searchPattern.search(noGaps))
288 int sequenceStartPosition = seq.findPosition(seqColStart);
289 recordMatch(seq, searchPattern, sequenceStartPosition);
295 * no match - advance columnIndex past this visible region
296 * so the next visible region (if any) is searched next
298 columnIndex = seqColEnd + 1;
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.
312 * @param searchPattern
313 * @param firstResiduePosition
316 protected boolean recordMatch(SequenceI seq, Regex searchPattern,
317 int firstResiduePosition)
320 * get start/end of the match in sequence coordinates
322 int offset = searchPattern.matchedFrom();
323 int matchStartPosition = firstResiduePosition + offset;
324 int matchEndPosition = matchStartPosition
325 + searchPattern.charsMatched() - 1;
328 * update columnIndex to next column after the start of the match
329 * (findIndex returns a value base 1, columnIndex is held base 0)
331 columnIndex = seq.findIndex(matchStartPosition);
334 * check that this match is not a subset of the previous one (JAL-2302)
336 List<SearchResultMatchI> matches = searchResults.getResults();
337 SearchResultMatchI lastMatch = matches.isEmpty() ? null
338 : matches.get(matches.size() - 1);
340 if (lastMatch == null || !lastMatch.contains(seq, matchStartPosition,
343 searchResults.addResult(seq, matchStartPosition, matchEndPosition);
351 * Does searches other than for residue patterns. Currently this includes
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>
357 * Answers true if a match is found, else false.
360 * @param searchString
361 * @param searchPattern
364 protected boolean doNonMotifSearches(SequenceI seq, String searchString,
368 * position sequence search to start of sequence
372 if (searchForResidueNumber(seq, searchString))
376 if (searchSequenceName(seq, searchPattern))
380 if (includeDescription && searchSequenceDescription(seq, searchPattern))
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.
393 * @param searchPattern
396 protected boolean searchSequenceDescription(SequenceI seq, Regex searchPattern)
398 String desc = seq.getDescription();
399 if (desc != null && searchPattern.search(desc) && !idMatch.contains(seq))
401 idMatch.addElement(seq);
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.
413 * @param searchPattern
416 protected boolean searchSequenceName(SequenceI seq, Regex searchPattern)
418 if (searchPattern.search(seq.getName()) && !idMatch.contains(seq))
420 idMatch.addElement(seq);
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
431 protected boolean searchForResidueNumber(SequenceI seq, String searchString)
435 int res = Integer.parseInt(searchString);
436 if (seq.getStart() <= res && seq.getEnd() >= res)
438 searchResults.addResult(seq, res, res);
441 } catch (NumberFormatException ex)
448 * Sets whether the search is case sensitive (default is no)
452 public void setCaseSensitive(boolean value)
454 this.caseSensitive = value;
458 * Sets whether search returns all matches. Default is to return the next
463 public void setFindAll(boolean value)
465 this.findAll = value;
469 * Returns the (possibly empty) list of sequences matched on sequence name or
474 public Vector<SequenceI> getIdMatch()
480 * Answers the search results (possibly empty) from the last search
484 public SearchResultsI getSearchResults()
486 return searchResults;
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.
496 public int getColumnIndex()
502 * Answers the offset in the alignment (0..) of the sequence in which the last
503 * match was found (if any)
507 public int getSequenceIndex()
509 return sequenceIndex;
513 * Sets whether search also searches in sequence description text (default is
518 public void setIncludeDescription(boolean value)
520 this.includeDescription = value;