Regex: match permutations of DNA sequence

Question

How do I make a regular expression to evaluate the following string?

TGATGCCGTCCCCTCAACTTGAGTGCTCCTAATGCGTTGC

and extract the pattern CTCCT.

The pattern must be 3 C's and 2 T's in any order.

I tried /[C | T]{5}/ but it matches CCCCT and TCCCC

Thanks in Advance.

Answer 1

Compute all permutations of "CTCCT" and concatenate them to a regex:

CCCTT|CCTCT|CCTTC|CTCCT|CTCTC|CTTCC|TCCCT|TCCTC|TCTCC|TTCCC

This pattern can be optimized:

C(?:C(?:T(?:CT|TC)|CTT)|T(?:C(?:CT|TC)|TCC))|T(?:C(?:C(?:CT|TC)|TCC)|TCCC)

var regex = new RegExp(/C(?:C(?:T(?:CT|TC)|CTT)|T(?:C(?:CT|TC)|TCC))|T(?:C(?:C(?:CT|TC)|TCC)|TCCC)/g);

var string = "TGATGCCGTCCCCTCAACTTGAGTGCTCCTAATGCGTTGC";

console.log(regex.exec(string));

This pattern doesn't find overlapping matches, e. g. there would only be one match in CCCTTCCC.

To find overlapping matches, use lookahead:

C(?=C(?=T(?=CT|TC)|CTT)|T(?=C(?=CT|TC)|TCC))|T(?=C(?=C(?=CT|TC)|TCC)|TCCC)

var regex = new RegExp(/C(?=C(?=T(?=CT|TC)|CTT)|T(?=C(?=CT|TC)|TCC))|T(?=C(?=C(?=CT|TC)|TCC)|TCCC)/g);

var string = "CCCTTCCC";

while ((match = regex.exec(string)) != null) {
    console.log(match.index, string.substring(match.index, match.index + 5));
}

Regex can only deal with a fairly limited number of permutations. If you want to match segments of possibly arbitrary size, use a non-regex solution:

function c3t2_optimized(str) {
  var c = 0, t = 0;
  for (var i = 0; i < str.length; ++i) {
    var last = str.charAt(i);
    if (last == 'C') ++c;
    else if (last == 'T') ++t;
    if (i > 4) {
      var first = str.charAt(i - 5);
      if (first == 'C') --c;
      else if (first == 'T') --t;
    }
    if (c == 3 && t == 2) return i - 4;
  }
  return -1;
}

var string = "TGATGCCGTCCCCTCAACTTGAGTGCTCCTAATGCGTTGC";
      
console.log(c3t2_optimized(string));

Or the same as above, just as a generator stepping through all possibly overlapping matches:

function* c3t2_optimized(str) {
  var c = 0, t = 0;
  for (var i = 0; i < str.length; ++i) {
    var last = str.charAt(i);
    if (last == 'C') ++c;
    else if (last == 'T') ++t;
    if (i > 4) {
      var first = str.charAt(i - 5);
      if (first == 'C') --c;
      else if (first == 'T') --t;
    }
    if (c == 3 && t == 2) yield i - 4;
  }
}

var string = "CCCTTCCC";

for (i of c3t2_optimized(string)) {
  console.log(i, string.substring(i, i + 5));
}

Performance comparison: https://jsfiddle.net/24qguege/7/

Firefox 47:

• 68.83ms - regex (see above)
• 97.51ms - non-regex (see above)
• 9582.39ms - Andrew Rueckert's answer (better readability)

Answer 2

This isn't the type of problem that is easily solved using Regular Expressions. It can be solved fairly straighforwardly with a simple function, however

 function c3t2(str) {
  var lowerCaseStr = str.toLowerCase();
  for (index = 0; index + 5 <= str.length; index++) {
    var substring = lowerCaseStr.substring(index, index + 5);
    var chars = substring.split("");
    if (chars.sort().join("") === "ccctt") {
      return index;
    }
  }

  return false;
}

Answer 3

There are online generators that will make a permutations list that are distinct using
letters. I used this tool here https://www.dcode.fr/permutations-generator and is descent.

Given that list I added an OR symbol | between each word which made it into a regex.

Taking this one step further I made it into a full regex trie which is what makes
all the search engines and word completion editors so fast.

There may be regex trie generators out there that can assist in this process. This is the fastest way to go. I used Regexformat 9 to create this trie and there are others. This one uses a refactor engine to compact it and make it faster.

The more distinct letters and the number of letters can add up where you need a tool
to construct these. Example: ABCDE generates 120 unique permutations. After constructing a trie it becomes:

A(?:B(?:C(?:DE|ED)|D(?:CE|EC)|E(?:CD|DC))|C(?:B(?:DE|ED)|D(?:BE|EB)|E(?:BD|DB))|D(?:C(?:BE|EB)|B(?:CE|EC)|E(?:BC|CB))|E(?:B(?:CD|DC)|C(?:BD|DB)|D(?:BC|CB)))|B(?:A(?:C(?:DE|ED)|D(?:CE|EC)|E(?:CD|DC))|C(?:A(?:DE|ED)|D(?:AE|EA)|E(?:AD|DA))|D(?:C(?:AE|EA)|A(?:CE|EC)|E(?:AC|CA))|E(?:A(?:CD|DC)|C(?:AD|DA)|D(?:AC|CA)))|C(?:A(?:B(?:DE|ED)|D(?:BE|EB)|E(?:BD|DB))|B(?:A(?:DE|ED)|D(?:AE|EA)|E(?:AD|DA))|D(?:B(?:AE|EA)|A(?:BE|EB)|E(?:AB|BA))|E(?:B(?:AD|DA)|A(?:BD|DB)|D(?:AB|BA)))|D(?:C(?:B(?:AE|EA)|A(?:BE|EB)|E(?:AB|BA))|B(?:C(?:AE|EA)|A(?:CE|EC)|E(?:AC|CA))|A(?:C(?:BE|EB)|B(?:CE|EC)|E(?:BC|CB))|E(?:A(?:BC|CB)|B(?:AC|CA)|C(?:AB|BA)))|E(?:A(?:B(?:CD|DC)|C(?:BD|DB)|D(?:BC|CB))|B(?:A(?:CD|DC)|C(?:AD|DA)|D(?:AC|CA))|C(?:B(?:AD|DA)|A(?:BD|DB)|D(?:AB|BA))|D(?:ABC|B(?:AC|CA)|C(?:AB|BA)|ACB))

which is extremely fast.

Note that there is another way to do this using regex without using a trie. It uses a little known way to count in regex.
It is a combination of a conditional (?(cond)yes|no) and a group quantity. (?:){5}

Since the problem requires 5 characters, three C and two T, using 5 capture variables as
flags, each distinct and one for each letter given a total count of letters .
A small regex can be crafted. Each time a letter is found, a capture variable flag gets set.
If no capture flags are available, the match fails.

Like this: (?:C(?(3)(?(2)(?(1)(?!)|())|())|())|T(?(5)(?(4)(?!)|())|())){5}
https://regex101.com/r/PEnzkR/1

Conditionals are supported by the JGsoft engine, Perl, PCRE, Python, and .NET. Ruby supports them starting with version 2.0. Languages such as Delphi, PHP, and R that have regex features based on PCRE also support conditionals.

Note that the performance is slower than making a full blown regex trie.
It is however limited by the number of capture groups, but any more than 10 is
highly unlikely needed.