How to extract substrings based on multiple criteria?

user_2110417 0
Viewed 92

I have thousands of strings arranged in following manner:

>String1 \(sub1|string1)
DIMMFIOYBVSYBE
EFMWUISCFIUBFMCIUOEFMIUIDEM

>String2 \(sub2|string2)
HVUYVMUYBOIIUMYTVU
SYOYVSCOUYCVUYVSUYVUSC

I want to extract some substrings based on certain conditions, such that the following substrings should be extracted. The substrings will be:

String1:

DIM        X
M          X
FIOYBVS
YBEEFM
WUISC      X
FIUBFMC    X
IUOEFM
IUIDEM

String2:

HVUYVM
UYBOIIUM
YTVUS
YOYVSC      X
OUYCVUYVS   X
UYVUSC      X

The conditions are:

  1. substring should end with either M or S
  2. M or S should not be succeeded by C
  3. Length of the substring should be ≥ 4 and ≤ 8 charters

In the above example list of substring the marked X will not be considered as they don't follow the criteria.

Expected output:

Name    Frequency    substrings
String1   4          FIOYBVS; YBEEFM; IUOEFM; IUIDEM
String2   3          HVUYVM; UYBOIIUM; YTVUS

I tried using the sliding window method mentioned here. It does not work for me. Any help appreciated.

string-matching python bash
4 Answers

The following requires two passes, but it satisfies your stated conditions:

import re

for name, string in (
    ('String1', 'DIMMFIOYBVSYBEEFMWUISCFIUBFMCIUOEFMIUIDEM'),
    ('String2', 'HVUYVMUYBOIIUMYTVUSYOYVSCOUYCVUYVSUYVUSC'),
    ):
    candidates = re.findall('[^MS]*[MS]C?', string)
    matches = [item for item in candidates
               if 4 <= len(item) <= 8 and not item.endswith('C')]
    print(f'{name}:    {len(matches)}    {"; ".join(matches)}')

Output:

String1:    4    FIOYBVS; YBEEFM; IUOEFM; IUIDEM
String2:    3    HVUYVM; UYBOIIUM; YTVUS
user_9844210 
str_1 = 'DIMMFIOYBVSYBEEFMWUISCFIUBFMCIUOEFMIUIDEM'
str_2 = 'HVUYVMUYBOIIUMYTVUSYOYVSCOUYCVUYVSUYVUSC'

strings = [str_1, str_2]
 
for s in strings:
    wrk = s
    print(s)
    print(40 * '-')
    while len(wrk) > 0:
        m = wrk.find('M') + 1
        s = wrk.find('S') + 1
        
        if (m < s and m > 0) or s <= 1:
            pos = m
        else:
            pos = s
        
        elem = wrk[ : pos]
        if wrk[pos : pos + 1] == 'C':
            elem += 'C'
            pos += 1

        if len(elem) >= 4 and len(elem) <= 8 and elem[-1:] != 'C':
            print(elem)
        else:
            print(elem + (20-len(elem)) * ' ' + 'X')
            
        wrk = wrk[pos : ]
    print()
#
#   R e s u l t 
#
'''
DIMMFIOYBVSYBEEFMWUISCFIUBFMCIUOEFMIUIDEM
----------------------------------------
DIM                 X
M                   X
FIOYBVS
YBEEFM
WUISC               X
FIUBFMC             X
IUOEFM
IUIDEM

HVUYVMUYBOIIUMYTVUSYOYVSCOUYCVUYVSUYVUSC
----------------------------------------
HVUYVM
UYBOIIUM
YTVUS
YOYVSC              X
OUYCVUYVS           X
UYVUSC              X
'''
user_190233530

Using 3 sed calls and an awk, this may work but may very well prove slower than python

$ cat script1.sed
/String/! {
    /^[[:upper:]]+$/ {
        N;s/\n//
    }
    s/([^MS]*(M|S)C?)/&\n/g
}

$ cat script2.sed
/^>/! { 
    /\<[[:upper:]]{4,8}\>/!d
    /(M|S)C/d
} 
1iName\tFrequency\tsubstrings

$ cat script3.sed
s/>?([^\n]*)\n/\1 /g
s/String[0-9]+/\n&\t/g
s/\\[^)]*\)//g
s/[[:upper:]]+\>/&;/g

Using the scripts, and adding an awk to count frequency, we can generate this;

sed -Ef script1.sed input_file | sed -Ef script2.sed | sed -Ezf script3.sed | awk  '/;/{$2=NF-1"\t\t"$2}1'
Name    Frequency   substrings 
String1 4       FIOYBVS; YBEEFM; IUOEFM; IUIDEM;
String2 3       HVUYVM; UYBOIIUM; YTVUS;
user_163721090

If awk is an option:

awk '
function parse_string() {
    sep=substrings=""
    freq=0
    while (string) {
          m1=match(string,/[MS]/)
          m2=match(string,/[MS]C/)

               if (m1 == m2)         string= substr(string,m1+2)
          else if (m1<4 || m1 > 8)   string= substr(string,m1+1)
          else if (m1)             { substrings= substrings sep substr(string,1,m1)
                                     sep="; "
                                     freq++
                                     string= substr(string,m1+1)
                                   }
          else                       string= ""
    }
    if (freq) print name,freq,substrings
}

BEGIN   { OFS="\t"; print "Name","Frequency","Substrings" }
/^>/    { name=substr($1,2); string=""; next }
NF      { string=string $0; next }
        { parse_string() }
END     { parse_string() }
' string.dat

This generates:

Name    Frequency       Substrings
String1 4       FIOYBVS; YBEEFM; IUOEFM; IUIDEM
String2 3       HVUYVM; UYBOIIUM; YTVUS

NOTE: assumes a single tab as output field delimiter is sufficient otherwise need details on output spacing requirements

user_73661000
Related