From 02781fd6e72716ac1638eeb2db0077eaf300c2e3 Mon Sep 17 00:00:00 2001 From: Jim Procter Date: Fri, 13 Nov 2015 12:24:51 +0000 Subject: [PATCH] JAL-1965 word based matching and explicit coping with match collisions - tests are failing --- src/jalview/analysis/SequenceIdMatcher.java | 170 +++++++++++++++++++--- test/jalview/analysis/SequenceIdMatcherTest.java | 32 +++- 2 files changed, 174 insertions(+), 28 deletions(-) diff --git a/src/jalview/analysis/SequenceIdMatcher.java b/src/jalview/analysis/SequenceIdMatcher.java index 8dda255..ad36ebe 100755 --- a/src/jalview/analysis/SequenceIdMatcher.java +++ b/src/jalview/analysis/SequenceIdMatcher.java @@ -26,8 +26,9 @@ import jalview.datamodel.SequenceI; import java.util.ArrayList; import java.util.Arrays; import java.util.HashMap; +import java.util.HashSet; import java.util.List; -import java.util.Vector; +import java.util.Set; /** * Routines for approximate Sequence Id resolution by name using string @@ -37,11 +38,63 @@ import java.util.Vector; */ public class SequenceIdMatcher { - private HashMap names; + /** + * weak hash for each sequence + */ + private HashMap> names; + + // /** + // * cache of values removed for each query string. + // */ + // private HashMap> resolved; + + /** + * do we index sequences on all 'words' in ID string ? + */ + private boolean wordBased = false; + + /** + * Characters that define the end of a unique sequence ID at the beginning of + * an arbitrary ID string JBPNote: This is a heuristic that will fail for + * arbritrarily extended sequence id's (like portions of an aligned set of + * repeats from one sequence) + */ + private static String WORD_SEP = "~. |#\\/<>!\"" + ((char) 0x00A4) + + "$%^*)}[@',?_"; + /** + * @return true if matcher is word-based (ie string key matches one of the + * words within the body of one or more sequence IDs) + */ + public boolean isWordBased() + { + return wordBased; + } + + /** + * Construct a standard (non-word based) matcher. To configure word based + * matching, use the fully qualified constructor + * + * @param seqs + */ public SequenceIdMatcher(List seqs) { - names = new HashMap(); + this(false, seqs); + } + + /** + * construct a new matcher for a set of sequences, configured as required. + * Note: enabling word based matching + * + * @param wordBasedMatch + * - when true, "myseq" matches "X|myseq" and "myseq" + * @param seqs + */ + public SequenceIdMatcher(boolean wordBasedMatch, + List seqs) + { + wordBased = wordBasedMatch; + names = new HashMap>(); addAll(seqs); } @@ -54,10 +107,35 @@ public class SequenceIdMatcher { for (SequenceI seq : seqs) { + addSeq(seq); + } + } + + private void addSeqIdName(SeqIdName idname, SequenceI seq) + { + Set seqset = names.get(idname); + if (seqset == null) + { + seqset = new HashSet(); + names.put(idname, seqset); + } + seqset.add(seq); + } + + public void addSeq(SequenceI seq) + { // TODO: deal with ID collisions - SequenceI should be appended to list // associated with this key. - names.put(new SeqIdName(seq.getDisplayId(true)), seq); + addSeqIdName(new SeqIdName(seq.getDisplayId(true)), seq); + if (wordBased) + { + for (SeqIdName key : getWordsFor(seq)) + { + addSeqIdName(key, seq); + } + } SequenceI dbseq = seq; + // TODO add test for database xref resolution while (dbseq.getDatasetSequence() != null) { dbseq = dbseq.getDatasetSequence(); @@ -72,15 +150,70 @@ public class SequenceIdMatcher sid = new SeqIdName(dbr[r].getAccessionId()); if (!names.containsKey(sid)) { - names.put(sid, seq); + addSeqIdName(sid, seq); } } + } + } + + + /** + * generate word based keys for the given sequence + * + * @param seq + * @return list of split keys + */ + public List getWordsFor(SequenceI seq) + { + ArrayList keys = new ArrayList(); + String name = seq.getName(), limits = "/" + seq.getStart() + "-" + + seq.getEnd(); + int namel = name.length(); + char[] sep = new char[WORD_SEP.length()]; + // find only the separators present in the ID. + for (int i = 0; i < sep.length; i++) + { + sep[i] = WORD_SEP.charAt(i); + if (seq.getName().indexOf("" + sep[i]) == -1) + { + sep[i] = 0; } } + ; + // make words + for (int i = 0; i < sep.length; i++) + { + if (sep[i] > 0) + { + int p = 0, m = -1; + while ((m = name.indexOf(sep[i], p)) > p) + { + + if (m > 0 && m - p > 5) + { + // split to end of word m with this delimiter + keys.add(new SeqIdName(name.substring(p, m - 1) + limits)); + } + if (namel - m > 5) + { + // index word after this delimiter m + keys.add(new SeqIdName(name.substring(m + 1) + limits)); + } + p = m + 1; + } + if (namel - p > 4) + { + // index word after this delimiter m + keys.add(new SeqIdName(name.substring(p) + limits)); + } + } + } + return keys; } /** - * convenience method to make a matcher from concrete array + * convenience method to make a matcher from concrete array Note: in order to + * support word based matching, use the fully qualified constructor * * @param sequences */ @@ -127,14 +260,14 @@ public class SequenceIdMatcher } SequenceI match = matches.remove(0); best.add(match); - names.put(new SeqIdName(match.getName()), match); + addSeq(match); int matchlen = match.getName().length(); int namlen = candName.id.length(); while (matches.size() > 0) { // look through for a better one. SequenceI cand = matches.remove(0); - names.put(new SeqIdName(cand.getName()), cand); + addSeq(cand); int q, w, candlen = cand.getName().length(); // keep the one with an id 'closer' to the given seqnam string if ((q = Math.abs(matchlen - namlen)) > (w = Math.abs(candlen @@ -245,10 +378,10 @@ public class SequenceIdMatcher private SequenceI findIdMatch( jalview.analysis.SequenceIdMatcher.SeqIdName nam) { - Vector matches = new Vector(); + ArrayList matches = new ArrayList(); while (names.containsKey(nam)) { - matches.addElement(names.remove(nam)); + matches.addAll(names.remove(nam)); } return pickbestMatch(nam, matches); } @@ -266,7 +399,7 @@ public class SequenceIdMatcher ArrayList matches = new ArrayList(); while (names.containsKey(nam)) { - matches.add(names.remove(nam)); + matches.addAll(names.remove(nam)); } List r = pickbestMatches(nam, matches); return r; @@ -318,15 +451,6 @@ public class SequenceIdMatcher } /** - * Characters that define the end of a unique sequence ID at the beginning - * of an arbitrary ID string JBPNote: This is a heuristic that will fail for - * arbritrarily extended sequence id's (like portions of an aligned set of - * repeats from one sequence) - */ - private String WORD_SEP = "~. |#\\/<>!\"" + ((char) 0x00A4) - + "$%^*)}[@',?_"; - - /** * matches if one ID properly contains another at a whitespace boundary. * TODO: (JBPNote) These are not efficient. should use char[] for speed * todo: (JBPNote) Set separator characters appropriately @@ -398,5 +522,11 @@ public class SequenceIdMatcher return check_wordmatch(s, id); } } + + @Override + public String toString() + { + return id; + } } } diff --git a/test/jalview/analysis/SequenceIdMatcherTest.java b/test/jalview/analysis/SequenceIdMatcherTest.java index a71d105..2a07ad5 100644 --- a/test/jalview/analysis/SequenceIdMatcherTest.java +++ b/test/jalview/analysis/SequenceIdMatcherTest.java @@ -24,6 +24,11 @@ public class SequenceIdMatcherTest return new SequenceIdMatcher(Arrays.asList(someseqs)); } + private static SequenceIdMatcher getWordMatcher() + { + return new SequenceIdMatcher(true, Arrays.asList(someseqs)); + } + @Test(groups = { "Functional" }) public void findSelfAndOthers() { @@ -36,15 +41,19 @@ public class SequenceIdMatcherTest + sq.getName() + "'"); SequenceI[] seqmatches = getMatcher().findIdMatch( new SequenceI[] { sq }); - Assert.assertTrue(seqmatches.length >= 1, - "Couldn't recover at least one sequence for sequence object called '" + Assert.assertEquals(1, seqmatches.length, + "Expected to recover one sequence for sequence object called '" + sq.getName() + "'"); - Assert.assertTrue(seqmatches.length == idmatches.length, - "Different matches found for '" + sq.getName() + "'"); - for (SequenceI sid : idmatches) + Assert.assertEquals(sq, seqmatches[0], + "Expected to recover the sequence queried with findIdMatch(SequenceI[])"); + // TODO: complexid and ComplexId are identical with case-insensitive + // matching. This assert fails because of this. + // Assert.assertTrue(seqmatches.length == idmatches.length, + // "Different matches found for '" + sq.getName() + "'"); + for (SequenceI sid : seqmatches) { boolean found = false; - for (SequenceI sobj : seqmatches) + for (SequenceI sobj : idmatches) { if (sid == sobj) { @@ -90,8 +99,15 @@ public class SequenceIdMatcherTest public void testFlankingMatch() { SequenceI[] match = getMatcher().findAllIdMatches("complexId"); - Assert.assertNotNull(match, "Flanking matches not found."); - Assert.assertEquals(match.length, 6, + // should find two matches - one case exact, the other case inexact. + Assert.assertNotNull(match, "Exact matches not found."); + Assert.assertEquals(match.length, 2, + "Expected two exact matches to be found."); + SequenceI[] fmatch = getWordMatcher() + .findAllIdMatches("complexId"); + // should find 6 distinct sequences + Assert.assertNotNull(fmatch, "Flanking matches not found."); + Assert.assertEquals(fmatch.length, 6, "Couldn't find all entries with IDs containing 'complexId' word match"); } -- 1.7.10.2