tour | Python Fiddle

#
import random

pick = ["A", "T", "C", "G"]

def picker():
	return pick[random.randrange(0, 4)]

def location_picker(length):
    return random.randrange(0, length)

def gene(size):
    new_gene = []
    while size > 0:
        new_gene += picker()
        size = size - 1
    return new_gene

def insert(gene):
    #have to say gene = insert(gene) after running function
    spot = location_picker(len(gene))
	return gene[:spot] + [picker()] + gene[spot:]

def delete(gene):
	spot = location_picker(len(gene))
    return gene[:spot] + gene[(spot + 1):]
"""
def transpose(gene):
    spot1 = location_picker(len(gene))
    spot2 = location_picker(len(gene))
    order = random.randrange(0, 3)
    if order == 0:
        return gene[spot1:spot2] + gene[:spot1] + gene[spot2:]
    elif order == 1:
        return gene[:spot1] + gene[spot1:spot2] + gene[spot2:]
    else:
		return gene[:spot1] + gene[spot2:] + gene[spot1:spot2]
"""    
def substitute(gene):
	spot = location_picker(len(gene))
   	gene[spot] = picker()
    return gene

def mutate(gene):
    #FIX!!!
	mutation = random.randrange(0, 3)
	if mutation == 0:
		return insert(gene)
	elif mutation == 1:
		return delete(gene)
	else:
		return substitute(gene)

##########################################

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)
    return selection_score

#shortest distance between children????????????????
def edit_distance(seq1, seq2):
    while len(seq1[0]) > 1 and len(seq2[0]) > 1:
        seq1 = seq1[0]
        seq2 = seq2[0]
    matrix = {}
    for x in range(len(seq1) + 1): 
        matrix[x, 0] = x
    for y in range(len(seq2) + 1): 
        matrix[0, y] = y
    for x in range(1, len(seq1) + 1):
        for y in range(1, len(seq2) + 1):
            if seq1[x - 1] == seq2[y - 1]:
                mismatch = 0 
            else:
                mismatch = 1
            matrix[x, y] = min(matrix[x, y - 1] + 1, matrix[x - 1, y] + 1, matrix[x - 1, y - 1] + mismatch)
    return matrix[x, y]

"""      
class nucleotides:
    def __init__(self):
        self.nucleotide = None # contains the data
        self.next = None # contains the reference to the next node

class gene():
    def __init__(self):
        self.cur_nucleotide = None

def add_nucleotide(self, insertion):
        new_nucleotide = nucleotides() # create a new node
        new_nucleotide.data = insertion
        new_nucleotide.next = self.cur_nucleotide # link the new node to the 'previous' node.
        self.cur_nucleotide = new_nucleotide #  set the current node to the new one.
        
    def generate(self, size):
        new_gene = gene()
        while size > 0:
            new_gene.add_nucleotide(picker())
            size = size - 1
            
    def insert(self, size):
        spot = location_picker(size)
        base = self.cur_nucleotide
        while spot > 0:
            base = self.next()
            #FIX!!!
            spot = spot - 1
        self.cur_nucleotide 
    def delete(self, size):
        spot = location_picker(size)
        
    def transpose(self, size):
    	spot = location_picker(size)
        
    def substitute(self, size):
		spot = location_picker(size)
        
    def mutate(self, size):
		mutation = random.randrange(0, 4)
        if mutation == 0:
            self.insert(size)
        elif mutation == 1:
            self.delete(size)
        elif mutation == 2:
            self.transpose(size)
        else:
            self.substitute(size)
            
    def list_print(self):
        nucleotide = self.cur_nucleotide
        while nucleotide:
            print nucleotide.insertion
            nucleotide = nucleotide.next
"""

###################################

class node:
    def __init__(self, ltree, top, rtree):
        self.top = top
        self.ltree = ltree
        self.rtree = rtree

def __repr__(self):
        return str(self.top)
    
class BT(node):
    def __init__(self, left=None, top=None, right=None):
        if top == None: # primitive
            self.rep = None
        else: # extending
            self.rep = node(left, top, right)
            
    def withEntry(self, key, value):
        return node([], [(key, value)], [])

def empty(self):
        return self.rep == None

def root(self):
        precondition(not self.empty())
        return self.rep.top

def left(self):
        precondition(not self.empty())
        return self.rep.ltree

def right(self):
        precondition(not self.empty())
        return self.rep.rtree

def size(self):
        if self.empty():
            return 0
        else:
            return self.left().size() + self.right().size() + 1

def __repr__(self): 
        #inorder traversal  
        a =[]
        if not self.empty():
            if not self.left().empty():
                a += self.left().__repr__()
            if not self.empty():
                a += [(self.root()[0][0], self.root()[0][1])]
            if not self.right().empty():
                a += self.right().__repr__()
        return a

#############
class BSTD(BT):
    """
    def rep_invariant(self):
        if self.empty():
            return True
        elif not self.left().empty():
            if self.left().root()[0][0] >= self.root()[0][0]:
                return False
        elif not self.right().empty():
            if self.right().root()[0][0] <= self.root()[0][0]:
                return False
        if self.left().rep_invariant() and self.left().rep_invariant():
            return True

# insert mutator without allowing duplicates
    def put(self, genes):
        if self.empty():
            self.rep = node(BSTD(), g, BSTD())
        #deciding where to put it
        index = 0
        best = 
        for x in genes:
            index += 1
            for y in genes[index:]:
                if edit_distance(x,y) < best:
                    best = edit_distance(x,y)
                
      """          
                
                #distances += ((x, y), edit_distance(x,y))
		#find smallest x[1], join x and y with distance root
            
	def tupler(self, genes):
        tuples = []
        while len(genes) > 1:
        	g1 = genes[0]
        	best = len(max(genes, key=len))
        	sibling = ""
        	for x in genes[1:]:
            	if edit_distance(g1, x) < best:
                	best = edit_distance(g1, x)
                	sibling = x
            tuples += [(g1, x)]
            genes = genes[1:]
        return tuples + [genes]
        
        
	def best_tuples(self, genes):

tuples = tupler(genes)
        while len(tuples) > len(genes)/2:
            g1 = tuples[0][0]
            g2 = tuples[0][1]
            for y in tuples[1:]:
            	if g1 == y[0]:
                    if edit_distance(g1, y[1]) =< edit_distance(g1, g2):
                        tuples = tuples[1:]
                    else:
                        tuples = tuples[:(tuples.index(y))] + tuples[(tuples.index(y)) + 1:]
                elif g1 == y[1]:
                    if edit_distance(g1, y[0]) =< edit_distance(g1, g2):
                        tuples = tuples[1:]
                    else:
                        tuples = tuples[:(tuples.index(y))] + tuples[(tuples.index(y)) + 1:]
        return best_tuple_lst
            
        
		#return (g1, sibling)
            
        
        
        #compare tuples via avg, rebuild tree every time 
        
        
"""
        best = selector(g, self.root())
        while (selector(g, self.left().root()) > best) or (selector(g, self.right().root()) > best):
            if selector(g, self.left().root()) > selector(g, self.right().root()):
                best = selector(g, self.left().root())
                self = self.left()
            else:
                self = self.right()
           		best = selector(g, self.right().root())
"""

Python Fiddle

Python Cloud IDE