# Graphs for Bioinformatics, Part 2: Finding Eulerian Paths

Posted in Computational Biology

# The Context: de Bruijn Graphs

In Part 1 of this post we discussed a data structure called a de Bruijn graph and covered its application to genome assembly. To summarize, a de Bruijn graph is a type of graph that represents a set of k-mers as a set of directed edges on …

# Graphs for Bioinformatics, Part 1: de Bruijn Graphs, Hamiltonian Paths, and Eulerian Paths

Posted in Computational Biology

# The Context: Rosalind.info

To provide a bit of context for a discussion of Euler paths and Euler cycles: starting around December, a group of us in the Lab for Data Intensive Biology (DIB Lab) started working through the textbook Bioinformatics Algorithms: An Active Learning Approach and the associated website, Rosalind.info.

Rosalind.info is a site that is similar in style …

# The Josephus Problem: Part 3: Solving the Double Step Case

Posted in Computer Science

This is Part 3 of an N-part series.

## Solving the Double Step Case

The Josephus Problem for a …

# The Josephus Problem: Part 2: Two Examples

Posted in Computer Science

This is Part 2 of an N-part series.

## Two Examples

In this blog post we'll walk through two examples of …

# The Josephus Problem: Part 1: The Problem

Posted in Computer Science

This is Part 1 of an N-part series.

## The Josephus Problem and Variations

The following problem, Cat and Mice, is Puzzle 88 in Boris Kordemsky's The Moscow Puzzles.

Purrer has decided to take a nap. He dreams …

# Five Letter Words: Part 5: The Try Trie Tree

Posted in Computer Science

In Volume 4 Fascicle 0 of Donald Knuth's Art of Computer Programming, Knuth introduces a tool for exploring concepts in graph theory: the five-letter words. This is a collection …

# Five Letter Words: Part 4: Revisiting Diff by One

Posted in Computer Science

In Volume 4, Facsimile 0 of Donald Knuth's Art of Computer Programming, in which Knuth covers graph theory, he introduces a list of five-letter words as part of a data set useful in exploring graph theory and graph algorithms.

The list of words is part of the Stanford Graph Base, a set of data sets that are useful for studying graph theory and networks.

See Five Letter Words on the charlesreid1.com wiki for details.

This post …

# Five Letter Words: Part 3: Letter Coverage and Dynamic Programming

Posted in Computer Science

NOTE: The code covered in this post uses Python 3. The scripts can be converted to Python 2 with minimal effort, but the author would encourage any user of Python 2 to "put on your big kid pants" and make the switch to Python 3. Let's all make this painful, drawn-out switch from Python 2 to Python 3 a thing of the past, shall we?

## Introduction

The letter/word coverage problem, as presented by Donald Knuth in Volume 4, Facicle 0 of his masterpiece Art of …

# Five Letter Words: Part 2: More Five-Word Algorithms

Posted in Computer Science

NOTE: The code covered in this post uses Python 3. The scripts can be converted to Python 2 with minimal effort, but the author would encourage any user of Python 2 to "put on your big kid pants" and make the switch to Python 3. Let's all make this painful, drawn-out switch from Python 2 to Python 3 a thing of the past, shall we?