Double Digest Problem

Given two sets of intervals on a common line segment between two disjoint interior point sets, and a third set of intervals between all points, reconstruct the positions of the points.

Input:

    dA - list of fragment lengths from the digest with enzyme A.
    dB - list of fragment lengths from the digest with enzyme B.
    dX - list of fragment lengths from the digest with both A and B.

Output:

    A – location of the cuts for the enzyme A.
    B – location of the cuts for the enzyme B.
In [78]:
# A collection of helper routines

def nextCount(s, maxval):
    # generates prod(maxval) states
    for i in reversed(xrange(len(s))):
        s[i] += 1
        if (s[i] <= maxval[i]):
            break
        s[i] = 0
    return s
In [82]:
# Let's test it

state = [0,0,0,0]
final = [1,2,1,3]

N = 0
while True:
    print "%3d: %s" % (N, state)
    if (state == final):
        break
    nextCount(state, final)
    N += 1
  0: [0, 0, 0, 0]
  1: [0, 0, 0, 1]
  2: [0, 0, 0, 2]
  3: [0, 0, 0, 3]
  4: [0, 0, 1, 0]
  5: [0, 0, 1, 1]
  6: [0, 0, 1, 2]
  7: [0, 0, 1, 3]
  8: [0, 1, 0, 0]
  9: [0, 1, 0, 1]
 10: [0, 1, 0, 2]
 11: [0, 1, 0, 3]
 12: [0, 1, 1, 0]
 13: [0, 1, 1, 1]
 14: [0, 1, 1, 2]
 15: [0, 1, 1, 3]
 16: [0, 2, 0, 0]
 17: [0, 2, 0, 1]
 18: [0, 2, 0, 2]
 19: [0, 2, 0, 3]
 20: [0, 2, 1, 0]
 21: [0, 2, 1, 1]
 22: [0, 2, 1, 2]
 23: [0, 2, 1, 3]
 24: [1, 0, 0, 0]
 25: [1, 0, 0, 1]
 26: [1, 0, 0, 2]
 27: [1, 0, 0, 3]
 28: [1, 0, 1, 0]
 29: [1, 0, 1, 1]
 30: [1, 0, 1, 2]
 31: [1, 0, 1, 3]
 32: [1, 1, 0, 0]
 33: [1, 1, 0, 1]
 34: [1, 1, 0, 2]
 35: [1, 1, 0, 3]
 36: [1, 1, 1, 0]
 37: [1, 1, 1, 1]
 38: [1, 1, 1, 2]
 39: [1, 1, 1, 3]
 40: [1, 2, 0, 0]
 41: [1, 2, 0, 1]
 42: [1, 2, 0, 2]
 43: [1, 2, 0, 3]
 44: [1, 2, 1, 0]
 45: [1, 2, 1, 1]
 46: [1, 2, 1, 2]
 47: [1, 2, 1, 3]

In [80]:
def compatible(x, y):
    i = 0
    for target in x:
        total = 0
        while (i < len(y)):
            total += y[i]
            i += 1
            if (total == target):
                break
            if (total > target):
                return False
        else:
            return False
    return True

def shift(l,s):
    lsize = len(l)
    return [l[(i+s)%lsize] for i in xrange(lsize)]

class Permute:
    def __init__(self, set):
        self.state = []
        self.setCopy = [item for item in set]
        self.order = [item for item in set]

    def nextPermutation(self):
        self.state = nextCount(self.state, [i for i in reversed(xrange(len(self.state)))])

    def permutationsRemain(self):
        if (len(self.state) == 0):
            # handle first time
            self.state = [0 for item in self.setCopy]
            return True
        else:
            self.nextPermutation()
            if (sum(self.state) != 0):
                t = [item for item in self.setCopy]
                self.order = [t.pop(i) for i in self.state]
                return True
            else:
                self.state = []
                self.order = [item for item in self.setCopy]
                return False
In []:
# The double digest solution from slide 11

def doubleDigest(seta, setb, setab, circular = False):
    a = Permute(seta)
    while (a.permutationsRemain()):
        ab = Permute(setab)
        while (ab.permutationsRemain()):
            if compatible(a.order, ab.order):
                b = Permute(setb)
                while (b.permutationsRemain()):
                    if (circular):
                        for i in xrange(len(setab)):
                            abShift = shift(ab.order, i)
                            if compatible(b.order, abShift):
                                return (a.order, b.order, ab.order, i)
                    else:
                        if compatible(b.order, ab.order):
                            return (a.order, b.order, ab.order, 0)
    return (aState, bState, abState, -1)
In [8]:
A = [1,2,3]
B = [2,4]
AB = [1,1,2,2]

aOrder, bOrder, abOrder, v = doubleDigest(A, B, AB)

print " A = ", aOrder
print " B = ", bOrder
print "AB = ", abOrder
 A =  [1, 2, 3]
 B =  [4, 2]
AB =  [1, 2, 1, 2]

Partial Digest Problem

Given all pairwise distances between points on a line, reconstruct the positions of those points.

Input:

    A multiset of pairwise distances L, of length (n2-n)/2.

Output:

    A set X, of n integers, such that the set of pairwise distances ΔX = L
In [20]:
def nextCombination(v, slots):
    for i in xrange(len(v)-1,-1,-1):
        v[i] += 1
        if (sum(v) > slots - len(v)):
            v[i] = 0
        else:
            break
    return v

class intsBetween:
    def __init__(self, l, h, c):
        self.state = list()
        self.low = l
        self.high = h
        self.count = c

    def intSet(self):
        v = [self.low]
        for i in xrange(len(self.state)):
            v.append(v[i]+self.state[i]+1)
        v.append(self.high)
        return v

    def combinationsRemain(self):
        if (len(self.state) == 0):
            # handles first time
            self.state = [0 for i in xrange(self.count)]
            return True
        else:
            nextCombination(self.state, self.high - self.low - 1)
            return (sum(self.state) != 0)

N = 0

def allPairsDist(L):
    global N
    N = N + 1
    dist = [L[j] - L[i] for i in xrange(len(L)-1) for j in xrange(i+1, len(L))]
    return dist
In [50]:
def valid(N):
    n = 2
    nC2 = 1
    while (nC2 <= N):
        if (nC2 == N):
            return n
        nC2 += n
        n += 1
    return 0
In [57]:
for v in xrange(200):
    n = valid(v)
    if (n > 0):
        print (n, v)
(2, 1)
(3, 3)
(4, 6)
(5, 10)
(6, 15)
(7, 21)
(8, 28)
(9, 36)
(10, 45)
(11, 55)
(12, 66)
(13, 78)
(14, 91)
(15, 105)
(16, 120)
(17, 136)
(18, 153)
(19, 171)
(20, 190)

In [73]:
def bruteForcePDP(L, n):
    L.sort()
    M = max(L)
    X = intsBetween(0,M,n-2)
    while (X.combinationsRemain()):
        dX = allPairsDist(X.intSet())
        dX.sort()
        if (dX == L):
            print "X =", X.intSet()
In [74]:
L = [2, 2, 3, 3, 4, 5, 6, 7, 8, 10]

if (valid(len(L)) > 0):
    bruteForcePDP(L, 5)
X = [0, 2, 4, 7, 10]
X = [0, 3, 6, 8, 10]

A more efficent Partial Digest solution:

In [75]:
class delta:
    def __init__(self, v, listOfInts):
        # constructs a multiset of distances from a given integer, v
        self.items = [abs(v - x) for x in listOfInts]

    def subset(self, listOfInts):
        # is the mutliset of deltas a subset of the given set of integers?
        listCopy = [i for i in listOfInts]
        for delta in self.items:
            if delta not in listCopy:
                return False
            else:
                listCopy.remove(delta)
        return True

def Place(L, X):
    if (len(L) == 0):
        print sorted(X)
        return
    y = max(L)           # Check distances from the "0" end
    dyX = delta(y, X)
    if (dyX.subset(L)):
        X.append(y); map(L.remove, dyX.items)
        Place(L, X)
        X.remove(y); map(L.append, dyX.items)
    w = max(X) - y      # Check distances from the "width" end
    dwX = delta(w, X)
    if (dwX.subset(L)):
        X.append(w); map(L.remove, dwX.items)
        Place(L, X)
        X.remove(w); map(L.append, dwX.items)
    return
In [76]:
def partialDigest(L):
    width = max(L)
    L.remove(width)
    X = [0, width]
    Place(L, X)
In [77]:
L = [2, 2, 3, 3, 4, 5, 6, 7, 8, 10]

if (valid(len(L)) > 0):
    partialDigest(L)
[0, 3, 6, 8, 10]
[0, 2, 4, 7, 10]

In []: