set 1

import heapq

def a_star(start, goal, heuristic):

open = []
heapq.heappush(open, (0, start))
closed = {}
cost_so_far = {start: 0}

while open:
    current = heapq.heappop(open)[1]

    if current == goal:
        path = []
        while current in closed:
            path.append(current)
            current = closed[current]
        path.append(start)
        path.reverse()
        return path

    for neighbor in neighbors(current): 
        new_cost = cost_so_far[current] + 1
        if neighbor not in cost_so_far or new_cost < cost_so_far[neighbor]:
            cost_so_far[neighbor] = new_cost
            priority = new_cost + heuristic(neighbor, goal)
            heapq.heappush(open, (priority, neighbor))
            closed[neighbor] = current

return None

def neighbors(s):

neighbors = set()

# insertions
for i in range(len(s) + 1):
    for c in 'AGTC':
        neighbor = s[:i] + c + s[i:]
        neighbors.add(neighbor)

# deletions
for i in range(len(s)):
    neighbor = s[:i] + s[i+1:]
    neighbors.add(neighbor)

# substitutions
for i in range(len(s)):
    for c in 'AGTC':
        neighbor = s[:i] + c + s[i+1:]
        neighbors.add(neighbor)

return neighbors

def dissimilarity(s1, s2):

dissimilarity = 0
for c1, c2 in zip(s1, s2):
    if c1 != c2:
        dissimilarity += 1
dissimilarity += abs(len(s1) - len(s2))
return dissimilarity

start = 'AGTCA'
goal = 'GGGGG'
heuristic = lambda s1, s2: dissimilarity(s1, s2)

path = a_star(start, goal, heuristic)

print(path)