Wrong result from StringCases with Shortest

Question

I have a list of strings like this:

test1 = {
"psi-mi:dvl1_mouse(display_long)|uniprotkb:Dvl1(gene name)|psi-mi:Dvl(display_short)|uniprotkb:Dvl(gene name synonym)|uniprotkb:DSH homolog 1(gene name synonym)",
"psi-mi:nxn_mouse(display_long)|uniprotkb:Nxn(gene name)|psi-mi:Nxn(display_short)|uniprotkb:Gn25(gene name synonym)|uniprotkb:Protein Red-1(gene name synonym)",
"psi-mi:lrp8_mouse(display_long)|uniprotkb:Apolipoprotein Ereceptor 2(gene name synonym)|uniprotkb:Lrp8(gene name)|psi-mi:Lrp8(display_short)|uniprotkb:Apoer2(gene name synonym)",
"psi-mi:reln_mouse(display_long)|uniprotkb:Reln(gene name)|psi-mi:Reln(display_short)|uniprotkb:Rl(gene name synonym)|uniprotkb:Reeler protein(gene name synonym)"}  

and I want to get the gene name, which is between the "uniprotkb:" and "(gene name)|". So I'm using StringCases and Shortest:

Map[StringCases[#, Shortest["|uniprotkb:" ~~ aa__ ~~ "(gene name)"] -> aa] &, test1]

and the result is

{{"Dvl1"},
 {"Nxn"},
 {"Apolipoprotein E receptor 2(gene name synonym)|uniprotkb:Lrp8"},
 {"Reln"}}

where the third element is not correct, because I just want to get "Lrp8". Can somebody tell me why this happens, and what should I do? Any suggestions will be appreciated. Thank you very much.

Answer 1

The behaviour we see here is due to the semantics of the regular expression pattern-matching process. Notionally, the string is scanned from left to right. At each character position, an attempt is made to match the string by looking ahead from that position. If there is no match, scanning moves onto the next character. If there is a match, then (by default) scanning resumes from the next character after the end of the match.

In the case at hand, consider what happens when the scanning position is the vertical bar at the beginning of the substring "|uniprotkb:Apolipoprotein". The scanner looks ahead from that position for a substring that ends "(gene name)". Since there are no constraints upon what the intervening characters (aa) will match, it happily scans right past a vertical bar and into what we consider to be the next entry. Having found match, it returns it and resumes scanning from the vertical bar introducing "|psi-mi:Lrp8".

There is some subtlety to meaning of the term Shortest. It does not mean find the shortest possible match relative to the lengths of other possible matches anywhere in the string. What it means is that the scanner, when looking ahead from any given position, is to stop as soon as it finds a match. The default (non-shortest) behaviour is to continue scanning, and to keep extending the match until there is no other possibility. The default behaviour is normally labelled by the jargon term "greedy". Mathematica's Shortest behaviour is usually labelled "lazy", or sometimes "reluctant".

A simple solution, as noted by @Kuba and @belisarius, is to constrain what can be matched by aa:

StringCases[test1, "|uniprotkb:" ~~ aa:Except["|"].. ~~ "(gene name)" :> aa]
(* {{"Dvl1"}, {"Nxn"}, {"Lrp8"}, {"Reln"}} *)

By excluding vertical bars from the intervening characters, we are essentially telling the scanner that it is not permitted to extend a match across entry boundaries.

Answer 2

StringCases[test1,"|uniprotkb:" ~~ aa : (WordCharacter ..) ~~ "(gene name)" ->  aa] 

(* {{"Dvl1"}, {"Nxn"}, {"Lrp8"}, {"Reln"}} *)

Answer 3

If you are strictly looking for the shortest string between "|uniprotkb:" and "(gene name)" in each record, this is a way :

StringCases[test1, "|uniprotkb:" ~~ x__ ~~ "(gene name)" :> x, Overlaps -> True] // 
(First@SortBy[#, StringLength] &) /@ # & 

{Dvl1,Nxn,Lrp8,Reln}

Answer 4

The code provided in the Question seems to be selecting the first instance rather than the Shortest, as can be seen by moving |uniprotkb:Lrp8(gene name) earlier in test1[[3]].

However, the following seems to work well.

StringCases[test1, "|uniprotkb:" ~~ aa__ ~~ "(gene name)" /; (StringLength[aa] <= 8) :> aa]

(* {{"Dvl1"}, {"Nxn"}, {"Lrp8"}, {"Reln"}} *)

Answer 5

MMA, V9:

StringCases[test1, __ ~~ "uniprotkb:" ~~ x__ ~~ "(gene name)|" :> x]
(*{{"Dvl1"}, {"Nxn"}, {"Lrp8"}, {"Reln"}}*)

Answer 6

Universal balanced Shortest

In this answer I managed to find a really universal solution through regular expressions:

Clear[ShortestStringBetween]
Options[ShortestStringBetween] = {"IncludeBoundaries" -> False, 
   "BoundaryOverlaps" -> False};
ShortestStringBetween[str_String, start_String, end_String, OptionsPattern[]] :=
  Module[{bInclude = OptionValue["IncludeBoundaries"],
    bOvelap = OptionValue["BoundaryOverlaps"]},
   Which[
    bInclude && Not[bOvelap],
    StringCases[str, RegularExpression[
      StringTemplate["`START`(?:(?!`END`).(?<!`START`))*`END`"][
       <|"START" -> start, "END" -> end|>]]],
    Not[bInclude] && Not[bOvelap],
    StringCases[str, RegularExpression[
       StringTemplate["`START`((?:(?!`END`).(?<!`START`))*)`END`"][
        <|"START" -> start, "END" -> end|>]] -> "$1"],
    Not[bInclude] && bOvelap,
    StringCases[str, RegularExpression[
      StringTemplate["(?<=`START`)(?:(?!`END`).(?<!`START`))*(?=`END`)"][
       <|"START" -> start, "END" -> end|>]]],
    bInclude && bOvelap,
    StringCases[str, match : RegularExpression[
        StringTemplate["(?<=`START`)(?:(?!`END`).(?<!`START`))*(?=`END`)"][
         <|"START" -> start, "END" -> end|>]] :> StringJoin[start, match, end]]
    ]];

Note that the start and end parameters are directly inserted into RegularExpression and therefore must be regular expressions in the Mathematica format. And since PCRE (on which RegularExpression is based) doesn't support infinite repetition within a lookbehind, the start parameter must be a fixed-length regexp or contain alternations of different but pre-determined lengths (for example, "cat|raccoon"). The end parameter has no such restriction. But I haven't tested how this implementation behaves with non-fixed length parameters.

It works correctly in the all test cases:

ShortestStringBetween[#, "\\|uniprotkb\\:", "\\(gene name\\)"] & /@ test1

{{"Dvl1"}, {"Nxn"}, {"Lrp8"}, {"Reln"}}

front = "Hello";
back = "Goodbye";
str = "blabla ...Hello Hello ... blabla ... Goodbye Goodbye ..";
ShortestStringBetween[str, front, back, "IncludeBoundaries" -> True]

{"Hello ... blabla ... Goodbye"}

front = "tomato";
back = "iconic";
str = "gffghtomatomato12345iconiconictomatomatoiconiconic";
ShortestStringBetween[str, front, back]

{"12345", ""}

front = "NotEnd";
back = "End";
str = "NotEndNotEnd1234NotEnd";
ShortestStringBetween[str, front, back]
ShortestStringBetween[str, front, back, "BoundaryOverlaps" -> True]

{"Not"}

{"Not", "1234Not"}