inito

HussainAther · Jan 31, 2020 · 58778dd · 58778dd
1 parent 776199b
commit 58778dd
Show file tree

Hide file tree

Showing 2 changed files with 169 additions and 0 deletions.
diff --git a/genomics/comp/bubble.py b/genomics/comp/bubble.py
@@ -0,0 +1,73 @@
+# python3
+import sys
+import itertools
+
+"""
+De Bruijn bubble detect
+"""
+
+class b:
+
+    def __init__(self, k, t, s):
+        self.k = k
+        self.t = t
+        self.g = {}
+        self.p = {}
+        self.l = 0
+
+        self.m = lambda v: self.g[v][1] > 1
+        self.o = lambda v: len(self.g[v][0]) > 1
+
+        self.bd_g(self.r(s))
+
+    def r(self, s):
+        a = lambda read: [read[j:j + self.k] for j in range(len(read) - self.k + 1)]
+        return [u for read in s for u in a(read)]
+
+    def bd_g(self, us):
+
+        def ae(g, l, h):
+            g.setdefault(l, [set(), 0])
+            g.setdefault(h, [set(), 0])
+
+            if h not in g[l][0]:
+                g[l][0].add(h)
+                g[h][1] += 1
+
+        for u in us:
+            l, h = u[:-1], u[1:]
+            if l != h:
+                ae(self.g, l, h)
+
+    def cl(self):
+        for k, v in self.g.items():
+            if self.o(k):
+                self.dfs(pt=[k], st=k, ce=k, dh=0)
+
+        for _, dl in self.p.items():
+            for pi in itertools.combinations(dl, r=2):
+                if self.pd(pi):
+                    self.l += 1
+
+        return self.l
+
+    def pd(self, pi):
+        return len(set(pi[0]) & set(pi[1])) == 2
+
+    def dfs(self, pt, st, ce, dh):
+        if ce != st and self.m(ce):
+            self.p.setdefault((st, ce), list()).append(pt[:])
+
+        if dh == self.t:
+            return
+
+        for n in self.g[ce][0]:
+            if n not in pt:
+                pt.append(n)
+                self.dfs(pt, st, n, dh + 1)
+                pt.remove(n)
+
+if __name__ == "__main__":
+    da = sys.stdin.read().split()
+    k, t, s = da[0], da[1], da[2:]
+    print(b(int(k), int(t), s).cl())
diff --git a/genomics/comp/removetip.py b/genomics/comp/removetip.py
@@ -0,0 +1,96 @@
+# python3
+import itertools
+import sys
+
+"""
+Remove tip with De Bruijn 
+"""
+
+class tr:
+    def __init__(self, k, ds):
+        self.k = k
+        self.th = self.k
+        self.g = {}
+        self.paths = {}
+        self.er = 0
+        self.bdb(self.br(ds))
+
+    def br(self, ds):
+        ak = lambda ew: [ew[j:j + self.k] for j in range(len(ew) - self.k + 1)]
+        return [m for ew in ds for m in ak(ew)]
+
+    def bdb(self, k):
+
+        def ag(g, e, h):
+            g.setdefault(e, [set(), 0])
+            g.setdefault(h, [set(), 0])
+            if h not in g[e][0]:
+                g[e][0].add(h)
+                g[h][1] += 1
+        for m in k:
+            e, h = m[:-1], m[1:]
+            if e != h:
+                ag(self.g, e, h)
+
+    def rt(self):
+        for k, z in self.g.items():
+            fa = None
+
+            if len(z[0]) == 1 and z[1] == 0:
+                fa = self.fain 
+            elif len(z[0]) > 1:
+                fa = self.faou 
+            else : continue
+
+            n = True
+            while n:
+                n = False
+                for edge in z[0]:
+                    if fa(edge, 0):
+                        z[0].remove(edge)
+                        self.er += 1
+                        n = True
+                        break
+
+        return self.er
+
+    def faou(self, c, d):
+        if self.ou(c) > 1 or self.inn(c) > 1:
+            return False
+
+        if d == self.th:
+            return False
+
+        if self.ou(c) == 0:
+            return True
+
+        if self.faou(next(iter(self.g[c][0])), d + 1):
+            self.g[c][0].pop()
+            self.er += 1
+            return True
+
+        return False
+
+    def fain(self, c, d):
+        if d == self.th:
+            return False
+
+        if self.ou(c) == 0 or self.inn(c) > 1:
+            return True
+
+        if self.fain(next(iter(self.g[c][0])), d + 1):
+            self.g[c][0].pop()
+            self.er += 1
+            return True
+
+        return False
+
+    def inn(self, z):
+        return self.g[z][1]
+
+    def ou(self, z):
+        return len(self.g[z][0])
+
+if __name__ == "__main__":
+    k, ds = 15, sys.stdin.read().split()
+    print(tr(k, ds).rt())