Pythonischer Weg, Strings zu "verschmelzen", alle möglichen Längen zu verarbeiten

Question

Ich versuche ein relativ häufiges Problem in der Bioinformatik zu lösen, ohne auf eine Menge if-Anweisungen zurückgreifen zu müssen.

Das Problem bei der Hand:

Ich bin bei zwei überlappenden Streichern und einer Länge der erwarteten Ausgang, und ich möchte eine fusionierte Kette erzeugen. Hier werden alle Möglichkeiten könnten die Saiten überlappen: (in den folgenden Beispielen eine - bedeutet, dass es nichts in dieser Zeichenfolge an dieser Position die consensus() Bit nach den Beispielen erläutert..):

# size=13 
xxxOVERLAP--- 
---OVERLAPyyy 
# expected output: xxx + consensus(xOVERLAP, yOVERLAP) + yyy 


# size=7 
---OVERLAPxxx 
yyyOVERLAP--- 
# expected output: consensus(xOVERLAP, yOVERLAP) 


# size=7 
OVERLAP 
OVERLAP 
# expected output: consensus(xOVERLAP, yOVERLAP) 

# size=10 
xxxOVERLAP 
---OVERLAP 
# expected output: xxx + consensus(xOVERLAP, yOVERLAP) 

# size=10 
OVERLAP--- 
OVERLAPyyy 
# expected output: consensus(xOVERLAP, yOVERLAP) + yyy 

# size > len(x) + len(y) 
# no overlap, produce error: 
xxx--- 
---yyy 
# expected output: error 

Die resultierende fusionierte Zeichenfolge muss beginnen mit dem Anfang von x und Ende mit dem Ende y. Die Region, die sich überschneidet, muss an eine andere Funktion übergeben werden, consensus(), die sich mit dem Zusammenführen der überlappten Region befasst. hier alle Möglichkeiten, die Saiten überlappen könnten: (in den folgenden Beispielen eine - zeigt, dass es nichts an dieser Position in dieser Zeichenfolge ist)

def merge(x, y, size): 
    # do the mergeing 
    return part of x that doesn't overlap + consensus(overlap) + part of y that doesn't overlap. 

ich ein Durcheinander von Code können, wenn Aussagen jeden Fall zu erkennen und sich individuell damit befassen, aber ich habe mich bemüht, eine elegantere Lösung zu finden. Ein Ansatz, den ich in Betracht gezogen habe, ist das Auffüllen der Strings (das Ende von x und der Anfang von y), so dass alle Fälle wie das zweite Beispiel aussehen, aber das scheint zu ineffizient, um schmackhaft zu sein, da ich dann neue Strings machen würde und ich wende diese Funktion an Millionen von Strings an.

Answer 1

würde ich mit einem Generator starten, die jedes Zeichen ergibt:

def merge_gen(x, y, overhang): 
    buffer = ' ' * overhang 
    for s in map(set, zip(buffer + x, y + buffer)): 
     yield max(s) 

Wo overhang ist len(x) - size (siehe unten)

Das funktioniert wie folgt:

>>> list(merge_gen('OVERLAPXXX', 'YYYOVERLAP', 3)) 
['Y', 'Y', 'Y', 'O', 'V', 'E', 'R', 'L', 'A', 'P', 'X', 'X', 'X'] 

Sie können dann implementieren eine merge Funktion einschließlich der consensus Funktion wie folgt:

Ich würde hoffen, dass dies in Python3 einigermaßen effizient ist; viele Generatoren, einige verschwendete Saiten, die weggeworfen werden müssen usw.

(*) Apparently Dies ist eine schnelle Möglichkeit, ein einzelnes Element aus einem Set zu erhalten. In diesem Fall wissen wir, dass das Set nur ein Element hat und wir wollen es nur extrahieren.

Answer 2

Ist das die Funktionalität, nach der Sie gesucht haben?

def consensus(left, right, ignore_blank_padding=True): 
    if ignore_blank_padding: 
     left = left.strip() 
     right = right.strip() 

    slide = len(left) + len(right) - 1 

    #slides the strings over each other one spot at a time 
    solutions = [] 
    for i in range(slide): 
     lft_test = left[-(i+1):] 
     rgt_test = right[:min(len(right), i+1)] 
     #print(lft_test, rgt_test) 
     if lft_test == rgt_test: 
      lft_garbage = left[:-(i+1)] 
      rgt_garbage = right[min(len(right), (i+1)):] 
      solutions.append((lft_garbage, lft_test, rgt_garbage)) 

    #if more than one overlap combo is found, keeps only the longest 
    if len(solutions) > 1: 
     sol_lenghts = [len(i[1]) for i in solutions]     
     longest_index = sol_lenghts.index(max(an_lens)) 
     solutions = solutions[longest_index] 
     return solutions 
    elif len(solutions) == 0: 
     return None 
    else: 
     return solutions[0] 

left = 'xxxxHEY' 
right = 'HEYxx' 
consensus(left, right) 
> ('xxxx', 'HEY', 'xx') 

left = 'xxHEYHEY' 
right = 'HEYHEYxxx' 
consensus(left, right) 
> ('xx', 'HEYHEY', 'xxx') 

left = 'xxHEY ' 
right = ' HEYHEYxxxx' 
consensus(left, right) 
> ('xx', 'HEY', 'HEYxxxx') 

left = 'HEY' 
right = ' HEYHEYxxxx' 
consensus(left, right) 
> ('', 'HEY', 'HEYxxxx') 

Links die alte Antwort mit dem Schiebefenster, aber hier ist es mit einer Überlappung angegeben:

def consensus(left, right, size, ignore_blank_padding=True): 
    if ignore_blank_padding: 
     left = left.strip() 
     right = right.strip() 

    solutions = None 
    lft_test = left[-(size):] 
    rgt_test = right[:size] 
    if lft_test == rgt_test: 
     lft_garbage = left[:-(size)] 
     rgt_garbage = right[min(len(right), (size)):] 
     solutions = (lft_garbage, lft_test, rgt_garbage) 

    return solutions 

left = 'xxxxHEY' 
right = 'HEYxx' 
consensus(left, right, 3) 
> ('xxxx', 'HEY', 'xx') 

left = 'xxHEYHEY' 
right = 'HEYHEYxxx' 
consensus(left, right, 6) 
> ('xx', 'HEYHEY', 'xxx') 

left = 'xxHEY ' 
right = ' HEYHEYxxxx' 
consensus(left, right, 3) 
> ('xx', 'HEY', 'HEYxxxx') 

left = 'HEY' 
right = ' HEYHEYxxxx' 
consensus(left, right, 3) 
> ('', 'HEY', 'HEYxxxx') 

Answer 3

Hier ist ein funktionierendes Beispiel, nutzt aber den „zu Art und Weise viele, wenn Aussagen“ Ansatz, ist schwer, schwer zu argumentieren über, und extrem unelegant zu lesen,:

def extra_left(x, y, size): 
    if size - len(y) > 0: 
     return x[:size - len(y)] 
    else: 
     return "" 


def extra_right(x, y, size): 
    if size - len(x) > 0: 
     return y[len(x) - size:] 
    else: 
     return "" 

def overlap(x, y, size): 

    if len(x) < size and len(y) < size: 
     x_overlap = x[size - len(y):] 
     y_overlap = y[:len(x) - size] 
    if len(x) < size and len(y) == size: 
     x_overlap = x 
     y_overlap = y[:len(x) - size] 
    if len(x) < size and len(y) > size: 
     x_overlap = x 
     y_overlap = y[len(y)-size:size] 

    if len(x) == size and len(y) < size: 
     x_overlap = x[size - len(y):] 
     y_overlap = y 
    if len(x) == size and len(y) == size: 
     x_overlap = x 
     y_overlap = y 
    if len(x) == size and len(y) > size: 
     x_overlap = x 
     y_overlap = y[len(y) - size:] 

    if len(x) > size and len(y) < size: 
     x_overlap = x[size - len(y):size] 
     y_overlap = y 
    if len(x) > size and len(y) == size: 
     x_overlap = x[:size] 
     y_overlap = y 
    if len(x) > size and len(y) > size: 
     x_overlap = x[:size] 
     y_overlap = y[-size:] 

    if len(x) + len(y) < size: 
     raise RuntimeError("x and y do not overlap with this size") 

    return consensus(x_overlap, y_overlap) 

def consensus(x, y): 
    assert len(x) == len(y) 
    return x 


def merge(x, y, size): 
    return extra_left(x, y, size) + overlap(x, y, size) + extra_right(x, y, size) 

Hier sind einige Unit-Tests (unter Verwendung von pytest)

class Tests: 

    def test1(self): 
     """ 
     len(x) < size and len(y) < size: 
     xxxOVERLAP--- 
     ---OVERLAPyyy 
     # expected output: xxx + consensus(xOVERLAP, yOVERLAP) + yyy 
     """ 
     x = "AAAATTTTTTT" 
     y = "TTTTTTTCCC" 
     size = 14 
     assert merge(x, y, size) == "AAAA" + consensus("TTTTTTT", "TTTTTTT") + "CCC" 

    def test2(self): 
     """ 
     if len(x) < size and len(y) == size: 
     # size=10 
     OVERLAP--- 
     OVERLAPyyy 
     # expected output: consensus(xOVERLAP, yOVERLAP) + yyy 
     """ 
     x = "TTTTTTT" 
     y = "TTTTTTTCCC" 
     size = 10 
     assert merge(x, y, size) == consensus("TTTTTTT", "TTTTTTT") + "CCC" 

    def test3(self): 
     """ 
     if len(x) < size and len(y) > size: 
     ---OVERLAP--- 
     yyyOVERLAPyyy 
     """ 
     x = "TTTTTTT" 
     y = "CCCTTTTTTTCCC" 
     size = 10 
     assert merge(x, y, size) == consensus("TTTTTTT", "TTTTTTT") + "CCC" 

    def test4(self): 
     """ 
     if len(x) == size and len(y) < size: 
     # size=10 
     xxxOVERLAP 
     ---OVERLAP 
     # expected output: xxx + consensus(xOVERLAP, yOVERLAP) 
     """ 
     x = "AAATTTTTTT" 
     y = "TTTTTTT" 
     size = 10 
     assert merge(x, y, size) == "AAA" + consensus("TTTTTTT", "TTTTTTT") 

    def test5(self): 
     """ 
     if len(x) == size and len(y) == size: 
     # size=7 
     OVERLAP 
     OVERLAP 
     # expected output: consensus(xOVERLAP, yOVERLAP) 
     """ 
     x = "TTTTTTT" 
     y = "TTTTTTT" 
     size = 7 
     assert merge(x, y, size) == consensus("TTTTTTT", "TTTTTTT") 

    def test6(self): 
     """ 
     if len(x) == size and len(y) > size: 
     # size=10 
     --xxxOVERLAP 
     yyyyyOVERLAP 
     # expected output: consensus(xOVERLAP, yOVERLAP) 
     """ 
     x = "AAATTTTTTT" 
     y = "CCCCCTTTTTTT" 
     size = 10 
     assert merge(x, y, size) == "AAA" + consensus("TTTTTTT", "TTTTTTT") 

    def test7(self): 
     """ 
     if len(x) > size and len(y) < size: 
     xxxOVERLAPxxx 
     ---OVERLAP--- 
     """ 
     x = "AAATTTTTTTAAA" 
     y = "TTTTTTT" 
     size = 10 
     assert merge(x, y, size) == "AAA" + consensus("TTTTTTT", "TTTTTTT") 

    def test8(self): 
     """ 
     if len(x) > size and len(y) == size: 
     ---OVERLAPxxx 
     ---OVERLAP--- 
     """ 
     x = "TTTTTTTAAA" 
     y = "TTTTTTT" 
     size = 7 
     assert merge(x, y, size) == consensus("TTTTTTT", "TTTTTTT") 

    def test9(self): 
     """ 
     if len(x) > size and len(y) > size: 
     ---OVERLAPxxx 
     yyyOVERLAP--- 
     # expected output: consensus(xOVERLAP, yOVERLAP) 
     """ 
     x = "TTTTTTTAAA" 
     y = "CCCTTTTTTT" 
     size = 7 
     assert merge(x, y, size) == consensus("TTTTTTT", "TTTTTTT") 


    def test_error(self): 
     """ 
     # no overlap, produce error: 
     xxx--- 
     ---yyy 
     # expected output: error 
     """ 
     x = "AAA" 
     y = "TTT" 
     size = 7 
     with pytest.raises(RuntimeError): 
      merge(x, y, size) 

Und sie alle passieren:

test_merge.py::Tests::test1 PASSED 
test_merge.py::Tests::test2 PASSED 
test_merge.py::Tests::test3 PASSED 
test_merge.py::Tests::test4 PASSED 
test_merge.py::Tests::test5 PASSED 
test_merge.py::Tests::test6 PASSED 
test_merge.py::Tests::test7 PASSED 
test_merge.py::Tests::test8 PASSED 
test_merge.py::Tests::test9 PASSED 
test_merge.py::Tests::test_error PASSED 

====================================================================== 10 passed in 0.02 seconds =======================================================================