Merging overlapping string sequences in a list

user_5823631 0
Viewed 255

I am trying to figure out how to merge overlapping strings in a list together, for example for

['aacc','accb','ccbe']

I would get

['aaccbe']

This following code works for the example above, however it does not provide me with the desired result in the following case:

s = ['TGT','GTT','TTC','TCC','CCC','CCT','CCT','CTG','TGA','GAA','AAG','AGC','GCG','CGT','TGC','GCT','CTC','TCT','CTT','TTT','TTT','TTC','TCA','CAT','ATG','TGG','GGA','GAT','ATC','TCT','CTA','TAT','ATG','TGA','GAT','ATT','TTC']
a = s[0]
b = s[-1]
final_s = a[:a.index(b[0])]+b

print(final_s) 
>>>TTC

My output is clearly not right, and I don't know why it doesn't work in this case. Note that I have already organized the list with the overlapping strings next to each other.

bioinformatics overlap list python string
2 Answers

You can use a trie to storing the running substrings and more efficiently determine overlap. When the possibility of an overlap occurs (i.e for an input string, there exists a string in the trie with a letter that starts or ends the input string), a breadth-first search to find the largest possible overlap takes place, and then the remaining bits of string are added to the trie:

from collections import deque
#trie node (which stores a single letter) class definition
class Node:
   def __init__(self, e, p = None):
      self.e, self.p, self.c = e, p, []
   def add_s(self, s):
      if s:
         self.c.append(self.__class__(s[0], self).add_s(s[1:]))
      return self

class Trie:
   def __init__(self):
      self.c = []
   def last_node(self, n):
      return n if not n.c else self.last_node(n.c[0])
   def get_s(self, c, ls):
      #for an input string, find a letter in the trie that the string starts or ends with.
      for i in c:
         if i.e in ls:
            yield i
         yield from self.get_s(i.c, ls) 
   def add_string(self, s):
      q, d = deque([j for i in self.get_s(self.c, (s[0], s[-1])) for j in [(s, i, 0), (s, i, -1)]]), []
      while q:
         if (w:=q.popleft())[1] is None:
            d.append((w[0] if not w[0] else w[0][1:], w[2], w[-1]))
         elif w[0] and w[1].e == w[0][w[-1]]:
            if not w[-1]:
               if not w[1].c:
                   d.append((w[0][1:], w[1], w[-1]))
               else:
                   q.extend([(w[0][1:], i, 0) for i in w[1].c])
            else:
               q.append((w[0][:-1], w[1].p, w[1], -1))
      if not (d:={a:b for a, *b in d}):
         self.c.append(Node(s[0]).add_s(s[1:]))
      elif (m:=min(d, key=len)):
         if not d[m][-1]:
            d[m][0].add_s(m)
         else:
            t = Node(m[0]).add_s(m)
            d[m][0].p = self.last_node(t)

Putting it all together

t = Trie()
for i in ['aacc','accb','ccbe']:
   t.add_string(i)

def overlaps(trie, c = ''):
   if not trie.c:
      yield c+trie.e
   else:
      yield from [j for k in trie.c for j in overlaps(k, c+trie.e)]

r = [j for k in t.c for j in overlaps(k)]

Output:

['aaccbe']
user_73267380

Use difflib.find_longest_match to find the overlap and concatenate appropriately, then use reduce to apply the entire list.

import difflib
from functools import reduce


def overlap(s1, s2):
    # https://stackoverflow.com/a/14128905/4001592
    s = difflib.SequenceMatcher(None, s1, s2)
    pos_a, pos_b, size = s.find_longest_match(0, len(s1), 0, len(s2))
    return s1[:pos_a] + s2[pos_b:]


s = ['aacc','accb','ccbe']


result = reduce(overlap, s, "")
print(result)

Output

aaccbe
user_40015920
Related