overlap_greedy.py

import itertools
from Bio import SeqIO

def overlap(read_a, read_b, min_length):
    start = 0
    while True:
        start = read_a.find(read_b[:min_length], start)
        if start == -1:
            return 0
        if read_b.startswith(read_a[start:]):
            return len(read_a) - start
        start += 1

def pick_maximal_overlap(reads, min_overlap):
    read_a, read_b = None, None
    best_olen = 0
    for a, b in itertools.permutations(reads, 2):
        olen = overlap(a, b, min_overlap)
        if olen > best_olen:
            read_a, read_b = a, b
            best_olen = olen

    return read_a, read_b, best_olen

def shortestSuperstring(file_name):
    sequences = SeqIO.parse(file_name, 'fasta')
    reads = list(map(lambda seq_rec: str(seq_rec.seq), sequences))
    min_overlap = len(reads[0]) // 2 + 1

    read_a, read_b, overlap_len = pick_maximal_overlap(reads, min_overlap)
    while overlap_len > 0:
        reads.remove(read_a)
        reads.remove(read_b)
        reads.append(read_a + read_b[overlap_len:])
        read_a, read_b, overlap_len = pick_maximal_overlap(reads, min_overlap)

    return ''.join(reads)