Tag Archives: Eulerian Path

Eulerian Tour & Path

# For example, if the input graph was
# [(1, 2), (2, 3), (3, 1)]
# A possible Eulerian tour would be [1, 2, 3, 1]

from collections import defaultdict
from random import choice
import itertools
def eulerian_tour(graph):
    tour=[]
    nodes=defaultdict(list)
    for s, e in graph:
        nodes[s].append(e)
        nodes[e].append(s)
    start = choice(nodes.keys())
    tour.append(start)
    while(len(nodes[start])>0):
        last = nodes[start].pop()
        tour.append(last)
        nodes[last].remove(start)
        start = last
    if list(itertools.chain(*nodes.values())):
        #print nodes
        for start in nodes:
            if start in tour and len(nodes[start])>0:
                index = tour.index(start)
                #print start, index, tour    
                while (len(nodes[start])>0):
                    last = nodes[start].pop()
                    nodes[last].remove(start)
                    index+=1
                    tour.insert(index, last)
                    start = last
                    #print tour
                    #print nodes
    return tour

graph = [(0, 1), (1, 5), (1, 7), (4, 5), (4, 8), (1, 6), (3, 7), (5, 9), (2, 4), (0, 4), (2, 5), (3, 6), (8, 9)]
eulerian_tour(graph)

Read more of this post

Advertisement

Graph, Eulerian Path, Eulerian Tour

Algorithms areGraph just how we organize computations to solve a particular problem. Some algorithms are really straightforward, but other algorithms take advantage of subtle mathematical properties to quickly and accurately provide an answer.

A set of circles and lines connecting between them is graph.
Read more of this post

Graph – Overlap, De Bruijn

1. String Composition: Form the k-mer composition of a string.
Input: An integer k and a string Text.
Output: Compositionk(Text), where the k-mers are written in lexicographic order.
Composition3(TATGGGGTGC) = ATG, GGG, GGG, GGT, GTG, TAT, TGC, TGG

dnas = [in_dna[i:i+k] for i in range(0, len(in_dna)) if len(in_dna[i:i+k])==k]
dnas.sort()

For example TAATGCCATGGGATGTT are linked together to form the genome path.

s1
For example, each of the three occurrences of ATG should be connected to TGC, TGG, and TGT; these connections are overlapping 3-mers. The graph showing all overlap connections.

s2
The structure in the figure above is an example of a graph, or a network of nodes connected by edges. This graph is an example of a directed graph, whose edges have a direction and are represented by arrows (as opposed to undirected graphs whose edges do not have directions).

Sequence much shorter DNA fragments called reads.

Read more of this post