Question: How To Generate The Graph Of The Genotype Space?
7
gravatar for Giovanni M Dall'Olio
7.7 years ago by
London, UK
Giovanni M Dall'Olio26k wrote:

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:

alt text

http://bioevo.upf.edu/~gdallolio/images/genotype_space.png

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!

network graph genotyping • 2.6k views
ADD COMMENTlink modified 7.7 years ago by Jts1.2k • written 7.7 years ago by Giovanni M Dall'Olio26k
11
gravatar for Jts
7.7 years ago by
Jts1.2k
Jts1.2k wrote:

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.

ADD COMMENTlink written 7.7 years ago by Jts1.2k
1

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

<script src="&lt;a href=" 1854319"="">1854319"></script>

ADD REPLYlink written 7.7 years ago by Giovanni M Dall'Olio26k

thanks! you are right, this is an Hamming graph.

ADD REPLYlink written 7.7 years ago by Giovanni M Dall'Olio26k
Please log in to add an answer.

Help
Access

Use of this site constitutes acceptance of our User Agreement and Privacy Policy.
Powered by Biostar version 2.3.0
Traffic: 1147 users visited in the last hour