scorer | Python Fiddle

def comparison(seq1, seq2):
    #precondition(type(seq2) = type(seq1) = type("a") and len(seq1) > 0 and len(seq2) > 0)
    #while shifting the alignment between 2 fragments by shortening one, look for a region of complete overlap, 
    index = len(seq1)
    if seq1 == seq2[:index]:
        return [index, seq1]
    else:
        return [0]
    #postcondition: return the index of the slicing when the overlap occurred and the length of the overlap
    #else, if no overlap found return 0

def selector(Seq1, Seq2):
    #precondition(type(seq2) = type(seq1) = type("a") and len(seq1) > 0 and len(seq2) > 0)
    #find the greateast score from different alignments generated by comparison(seq1, seq2)
    sequence1 = ""
    selection_score = 0
    for x in range(len(Seq1)):
        seq1 = Seq1[x:]
        selection = comparison(seq1, Seq2)
        if selection[0]>selection_score:
            selection_score=selection[0]
            sequence1 = Seq1+Seq2[len(Seq1)-x:]
    #postcondition: return the best score (highest value of selection_score attained) and a concatenation of the two sequences when they were overlapping
    return [selection_score, sequence1]

"""

def combiner(Seq1, Seq2):
    #precondition(type(seq2) = type(seq1) = type("a") and len(seq1) > 0 and len(seq2) > 0)
    #assemble a list of all the scores and their concatenations generated by selector for 2 sequences in backwards and forwards orientations
    matrix = []
    matrix.append(selector(Seq1, Seq2))
    #both forwards
    matrix.append(selector(Seq1, (Seq2[::-1])))
    #seq2 backwards
    matrix.append(selector((Seq1[::-1]), Seq2))
    #seq1 backwards
    matrix.append(selector((Seq1[::-1]), (Seq2[::-1])))
    #both backwards

sequence1_index = 0
    combiner_score = 0
    for x in range(4):
        if combiner_score <= matrix[x][0]:
            sequence1_index = x
            combiner_score= matrix[x][0]
    #compare scores to find which orientation yields the best overlap
    #postcondition: combiner_score is the highest value of matrix[x][0] produced by any alignment
    return matrix[sequence1_index]

def assembler(fragments):
    #precondition(type(fragments) = type(["a", "b"]) and len(fragments) > 0 and type(fragments[0]) = type("a"))
    #find which fragment compares best with a given fragment in the list of fragments, i.e. the highest combiner value produced using any fragment in the list compared to the firt
    assembler_score  = 0
    final_score = "select"
    sequence1_index = 0
    sequence2_index = 0
    for x in range(len(fragments)):
        for y in range(x+1, len(fragments)):
            score = combiner(fragments[x],fragments[y])
            if score[0] > assembler_score:
                assembler_score = score[0]
                final_score = score
                sequence1_index = x
                sequence2_index = y
    #postcondition: final_score >= score, sequence indexes indicate the two fragments that make the best pair (have the most overlap)
    return [final_score, sequence1_index, sequence2_index]

def genome(fragments):
    #precondition(type(fragments) = type(["a", "b"]) and len(fragments) > 0 and type(fragments[0]) = type("a"))
    #removes fragments from the list once they have been paired with their best match and repeats the pairing process until only one fragment is left
    assembled = assembler(fragments)
    if assembled[0] == "select":
        return fragments
    else: 
        fragments[assembled[1]] = "select"
        fragments[assembled[2]] = "select"
    fragments.remove("select")
    fragments.remove("select")
    fragments.append(assembled[0][1])
    #postcondition: len(genome) = 1 and genome[0] is the shortest possible string formed from concatenating all fragments, i.e. omitting the most overlap
    return genome(fragments)

X=["cat", "att", "cg"]
print genome(X)

"""

Python Fiddle

Python Cloud IDE