How To Generate The Graph Of The Genotype Space?

Question

[Giovanni M Dall'Olio]

The genotype space is a representation of all the possible genotypes that an organism can have, in which two neighbor points are different only for one single mutation.

For example, imagine that the genome of an organism is composed by only 5 bases, and that each base can only have two types of bases. The genotype space would look like the following graph:

Link to image

If you look at the figure, each node is connected only to nodes that have only one single difference. For example, "00000" is connected to "10000", "01000", "00100", "00010" and "00001".

Does anyone know if this kind of graph has a name, or if there is some computational way to generate it for bigger genomes? Each half of the graph is a rooted tree, but then, I don't know how I could connect the two parts programmatically.

Thank you in advance!

Answer 1

[Jts]

In such a graph for n genotypes you have a vertex for all possible 2^n binary strings. Edges connect vertices that have a hamming distance of 1. This is the hamming graph H(n, 2).

To generate such a graph, start by making a vertex for all 2^n binary strings. Then for each vertex you can generate the n neighbors by flipping each bit of the vertex label.

[Giovanni M Dall'Olio]

Here is a quick-and-dirty python implementation to generate an Hamming graph:

	#!/usr/bin/env python
	"""
	Generate a Hamming Graph
	"""
	import networkx
	import itertools
	import logging
	def hamming_binary(chromosome_len):
	"""Generate a binary Hamming Graph, where each genotype is composed by chromosome_len bases and each base can take only two values. H(chromosome_len, 2).
	steps to generate an Hamming graph:
	* create 2^chromosome_len nodes, each for a different binary string
	* for each node, find the connected nodes by flipping one position at a time.
	"""
	space = networkx.Graph()
	# create all nodes
	l = ["01"] * chromosome_len
	all_nodes = itertools.product(*l)
	all_nodes = [''.join(x) for x in all_nodes]
	logging.debug(all_nodes)
	space.add_nodes_from(all_nodes)
	# for each node, find neighbors
	for node in space.nodes():
	[space.add_edge(node, mutate_node(node, base)) for base in range(chromosome_len)]
	return space
	def mutate_node(node, n):
	# wonder if there is some binary utils package for python
	if node[n] == '0':
	newbase = '1'
	else:
	newbase = '0'
	new_node = node[0:n] + newbase + node[n+1:]
	return new_node
	if __name__ == '__main__':
	logging.basicConfig(level=logging.DEBUG)
	space = hamming_binary(5)

view raw gistfile1.py hosted with ❤ by GitHub

[Giovanni M Dall'Olio]

Thanks! You are right, this is an Hamming graph.