Merge remote-tracking branch 'origin/tasks/JAL-3035_remove_dasobert_dependency' into...
[jalview.git] / src / jalview / analysis / SequenceIdMatcher.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.DBRefEntry;
24 import jalview.datamodel.SequenceI;
25
26 import java.util.ArrayList;
27 import java.util.Arrays;
28 import java.util.HashMap;
29 import java.util.List;
30 import java.util.Vector;
31
32 /**
33  * Routines for approximate Sequence Id resolution by name using string
34  * containment (on word boundaries) rather than equivalence. It also attempts to
35  * resolve ties where no exact match is available by picking the the id closest
36  * to the query.
37  */
38 public class SequenceIdMatcher
39 {
40   private HashMap<SeqIdName, SequenceI> names;
41
42   public SequenceIdMatcher(List<SequenceI> seqs)
43   {
44     names = new HashMap<SeqIdName, SequenceI>();
45     addAll(seqs);
46   }
47
48   /**
49    * Adds sequences to this matcher
50    * 
51    * @param seqs
52    */
53   public void addAll(List<SequenceI> seqs)
54   {
55     for (SequenceI seq : seqs)
56     {
57       add(seq);
58     }
59   }
60
61   /**
62    * Adds one sequence to this matcher
63    * 
64    * @param seq
65    */
66   public void add(SequenceI seq)
67   {
68     // TODO: deal with ID collisions - SequenceI should be appended to list
69     // associated with this key.
70     names.put(new SeqIdName(seq.getDisplayId(true)), seq);
71     SequenceI dbseq = seq;
72     while (dbseq.getDatasetSequence() != null)
73     {
74       dbseq = dbseq.getDatasetSequence();
75     }
76     // add in any interesting identifiers
77     if (dbseq.getDBRefs() != null)
78     {
79       DBRefEntry dbr[] = dbseq.getDBRefs();
80       SeqIdName sid = null;
81       for (int r = 0; r < dbr.length; r++)
82       {
83         sid = new SeqIdName(dbr[r].getAccessionId());
84         if (!names.containsKey(sid))
85         {
86           names.put(sid, seq);
87         }
88       }
89     }
90   }
91
92   /**
93    * convenience method to make a matcher from concrete array
94    * 
95    * @param sequences
96    */
97   public SequenceIdMatcher(SequenceI[] sequences)
98   {
99     this(Arrays.asList(sequences));
100   }
101
102   /**
103    * returns the closest SequenceI in matches to SeqIdName and returns all the
104    * matches to the names hash.
105    * 
106    * @param candName
107    *          SeqIdName
108    * @param matches
109    *          List of SequenceI objects
110    * @return SequenceI closest SequenceI to SeqIdName
111    */
112   private SequenceI pickbestMatch(SeqIdName candName,
113           List<SequenceI> matches)
114   {
115     List<SequenceI> st = pickbestMatches(candName, matches);
116     return st == null || st.size() == 0 ? null : st.get(0);
117   }
118
119   /**
120    * returns the closest SequenceI in matches to SeqIdName and returns all the
121    * matches to the names hash.
122    * 
123    * @param candName
124    *          SeqIdName
125    * @param matches
126    *          Vector of SequenceI objects
127    * @return Object[] { SequenceI closest SequenceI to SeqIdName, SequenceI[]
128    *         ties }
129    */
130   private List<SequenceI> pickbestMatches(SeqIdName candName,
131           List<SequenceI> matches)
132   {
133     ArrayList<SequenceI> best = new ArrayList<SequenceI>();
134     if (candName == null || matches == null || matches.size() == 0)
135     {
136       return null;
137     }
138     SequenceI match = matches.remove(0);
139     best.add(match);
140     names.put(new SeqIdName(match.getName()), match);
141     int matchlen = match.getName().length();
142     int namlen = candName.id.length();
143     while (matches.size() > 0)
144     {
145       // look through for a better one.
146       SequenceI cand = matches.remove(0);
147       names.put(new SeqIdName(cand.getName()), cand);
148       int q, w, candlen = cand.getName().length();
149       // keep the one with an id 'closer' to the given seqnam string
150       if ((q = Math.abs(matchlen - namlen)) > (w = Math
151               .abs(candlen - namlen)) && candlen > matchlen)
152       {
153         best.clear();
154         match = cand;
155         matchlen = candlen;
156         best.add(match);
157       }
158       if (q == w && candlen == matchlen)
159       {
160         // record any ties
161         best.add(cand);
162       }
163     }
164     if (best.size() == 0)
165     {
166       return null;
167     }
168     ;
169     return best;
170   }
171
172   /**
173    * get SequenceI with closest SequenceI.getName() to seq.getName()
174    * 
175    * @param seq
176    *          SequenceI
177    * @return SequenceI
178    */
179   public SequenceI findIdMatch(SequenceI seq)
180   {
181     SeqIdName nam = new SeqIdName(seq.getName());
182     return findIdMatch(nam);
183   }
184
185   public SequenceI findIdMatch(String seqnam)
186   {
187     SeqIdName nam = new SeqIdName(seqnam);
188     return findIdMatch(nam);
189   }
190
191   /**
192    * Find all matches for a given sequence name.
193    * 
194    * @param seqnam
195    *          string to query Matcher with.
196    * @return a new array or (possibly) null
197    */
198   public SequenceI[] findAllIdMatches(String seqnam)
199   {
200
201     SeqIdName nam = new SeqIdName(seqnam);
202     List<SequenceI> m = findAllIdMatches(nam);
203     if (m != null)
204     {
205       return m.toArray(new SequenceI[m.size()]);
206     }
207     return null;
208   }
209
210   /**
211    * findIdMatch
212    * 
213    * Return pointers to sequences (or sequence object containers) which have
214    * same Id as a given set of different sequence objects
215    * 
216    * @param seqs
217    *          SequenceI[]
218    * @return SequenceI[]
219    */
220   public SequenceI[] findIdMatch(SequenceI[] seqs)
221   {
222     SequenceI[] namedseqs = null;
223     int i = 0;
224     SeqIdName nam;
225
226     if (seqs.length > 0)
227     {
228       namedseqs = new SequenceI[seqs.length];
229       do
230       {
231         nam = new SeqIdName(seqs[i].getName());
232
233         if (names.containsKey(nam))
234         {
235           namedseqs[i] = findIdMatch(nam);
236         }
237         else
238         {
239           namedseqs[i] = null;
240         }
241       } while (++i < seqs.length);
242     }
243
244     return namedseqs;
245   }
246
247   /**
248    * core findIdMatch search method
249    * 
250    * @param nam
251    *          SeqIdName
252    * @return SequenceI
253    */
254   private SequenceI findIdMatch(
255           jalview.analysis.SequenceIdMatcher.SeqIdName nam)
256   {
257     Vector matches = new Vector();
258     while (names.containsKey(nam))
259     {
260       matches.addElement(names.remove(nam));
261     }
262     return pickbestMatch(nam, matches);
263   }
264
265   /**
266    * core findIdMatch search method for finding all equivalent matches
267    * 
268    * @param nam
269    *          SeqIdName
270    * @return SequenceI[]
271    */
272   private List<SequenceI> findAllIdMatches(
273           jalview.analysis.SequenceIdMatcher.SeqIdName nam)
274   {
275     ArrayList<SequenceI> matches = new ArrayList<SequenceI>();
276     while (names.containsKey(nam))
277     {
278       matches.add(names.remove(nam));
279     }
280     List<SequenceI> r = pickbestMatches(nam, matches);
281     return r;
282   }
283
284   class SeqIdName
285   {
286     String id;
287
288     SeqIdName(String s)
289     {
290       if (s != null)
291       {
292         id = s.toLowerCase();
293       }
294       else
295       {
296         id = "";
297       }
298     }
299
300     @Override
301     public int hashCode()
302     {
303       return ((id.length() >= 4) ? id.substring(0, 4).hashCode()
304               : id.hashCode());
305     }
306
307     @Override
308     public boolean equals(Object s)
309     {
310       if (s == null)
311       {
312         return false;
313       }
314       if (s instanceof SeqIdName)
315       {
316         return this.stringequals(((SeqIdName) s).id);
317       }
318       else
319       {
320         if (s instanceof String)
321         {
322           return this.stringequals(((String) s).toLowerCase());
323         }
324       }
325
326       return false;
327     }
328
329     /**
330      * Characters that define the end of a unique sequence ID at the beginning
331      * of an arbitrary ID string JBPNote: This is a heuristic that will fail for
332      * arbritrarily extended sequence id's (like portions of an aligned set of
333      * repeats from one sequence)
334      */
335     private String WORD_SEP = "~. |#\\/<>!\"" + ((char) 0x00A4)
336             + "$%^*)}[@',?_";
337
338     /**
339      * matches if one ID properly contains another at a whitespace boundary.
340      * TODO: (JBPNote) These are not efficient. should use char[] for speed
341      * todo: (JBPNote) Set separator characters appropriately
342      * 
343      * @param s
344      * @return boolean
345      */
346     private boolean stringequals(String s)
347     {
348       if (id.length() > s.length())
349       {
350         return id.startsWith(s)
351                 ? (WORD_SEP.indexOf(id.charAt(s.length())) > -1)
352                 : false;
353       }
354       else
355       {
356         return s.startsWith(id)
357                 ? (s.equals(id) ? true
358                         : (WORD_SEP.indexOf(s.charAt(id.length())) > -1))
359                 : false;
360       }
361     }
362
363     /**
364      * toString method returns the wrapped sequence id. For debugging purposes
365      * only, behaviour not guaranteed not to change.
366      */
367     @Override
368     public String toString()
369     {
370       return id;
371     }
372   }
373 }