I am looking for python code to perform a run length encoding to obtain a regex-like summary of a string s, for a known length k for the blocks. How should I tackle this?
e.g.
s=TATTTTATTTTATTTTATGTTATGTTATGTTATGTTATGTTATGTTATGTTATGTTATGTTACATTATTTTA
with k=5 could become
(TATTT)3(TATGT)9TACATTATTTTA
Instead of a regex pattern, you could split and group with itertools.groupby:
from itertools import groupby
s = "TATTTTATTTTATTTTATGTTATGTTATGTTATGTTATGTTATGTTATGTTATGTTATGTTACATTATTTTA"
k = 5
parts = [s[i:i+k] for i in range(0, len(s), k)]
for k, g in groupby(parts):
print(k, len(list(g)))
For your specific string this would yield
TATTT 3
TATGT 9
TACAT 1
TATTT 1
TA 1
Or - if you need to stick with your specific format as well:
lst = []
for k, g in groupby(parts):
_len = len(list(g))
if _len > 1:
lst.append(f"({k}){_len}")
else:
lst.append(k)
print("".join(lst))
# (TATTT)3(TATGT)9TACATTATTTTA
Use a capture group and back-reference to match repeated strings.
k=5
s='TATTTTATTTTATTTTATGTTATGTTATGTTATGTTATGTTATGTTATGTTATGTTATGTTACATTATTTTA'
rx = re.compile(rf'(.{{{k}}})\1*')
matches = rx.finditer(s)
output = ''
total_len = 0
for match in matches:
repeats = len(match.group()) // k
total_len += len(match.group())
if repeats == 1:
output += match.group(1)
else:
output += f'({match.group(1)}){repeats}'
# Get the unmatched part at the end
output += s[total_len:]
print(output)
I slightly modified the answer from @Jan to provide the shortest out of the k possible encodings (with k different start sites for the first block). This can make quite a difference, for some cases.
from itertools import groupby
def rle(sequence, motif_length):
solutions = []
for start in range(0, motif_length):
parts = [sequence[i : i + motif_length] for i in range(start, len(sequence), motif_length)]
lst = [sequence[0:start] if start > 0 else '']
for k, g in groupby(parts):
_len = len(list(g))
if _len > 1:
lst.append(f"({k}){_len}")
else:
lst.append(k)
solutions.append("".join(lst))
# return the shortest solution
return min(solutions, key=len)
rle("TATTTTATTTTATTTTATGTTATGTTATGTTATGTTATGTTATGTTATGTTATGTTATGTTACATTATTTTA", 5)
rle("TCTTTTATTTTATTTTATTTTATTTTATTTTATTTTATTTTATTTTATTTTATTTTA", 5)
I don't know Python but you could translate this PHP code if you'd like:
$s = 'TATTTTATTTTATTTTATGTTATGTTATGTTATGTTATGTTATGTTATGTTATGTTATGTTACATTATTTTA';
$k = 5;
echo preg_replace_callback( '/(.{'.$k.'})\1+/', function( $matches ) use ( $k ) {
return '('.$matches[ 1 ].')'.( strlen( $matches[ 0 ] ) / $k );
}, $s );
(TATTT)3(TATGT)9TACATTA(T)4A?(.{5})\1*to look for all the repetitions of a 5-character sequence.(.{5})\1+, no? Also, for OP I think the pseudo-code would be capture usingk, surround in parenthesis, divide capture byk, append number after close parenthesis