colelyman / kleuren

Find bubbles in the Colored de Bruijn Graph to reconstruct phylogenetic trees

kleuren

Find bubbles in the Colored de Bruijn Graph (CdBG) to reconstruct phylogenetic trees.

Installation

kleuren uses the CMake (>= version 3.1) build system to compile and link its dependencies. Thus, in order to use kleuren, one must have CMake installed.

CMake on Ubuntu

If you have super-user priveleges then you can install CMake by running

sudo apt-get install cmake

If you are running Ubuntu version 14.04 or earlier, then most likely the version that you have installed is too old to be compatible with kleuren (< version 3.1). You can download a CMake binary yourself, or add a PPA to install a newer version of CMake via the following commands

sudo apt-get install software-properties-common
sudo add-apt-repository ppa:george-edison55/cmake-3.x
sudo apt-get update
sudo apt-get upgrade

and an up-to-date version of CMake will be installed for you.

CMake on Mac OS X

If you have Homebrew installed, then just run

brew install cmake

and you are good to go!

After CMake is Installed

Once CMake is installed, run the following commands to clone the kleuren repo and compile the project

git clone --recursive https://github.com/Colelyman/kleuren.git
cd kleuren
mkdir build
cd build && cmake ..
make

there will be the kleuren executable in the ./bin/ folder of the root directory of the project. Thus, to run kleuren from the root directory of the project, you can simply execute

./bin/kleuren

and you have just run kleuren!

If you need to link against kleuren to use it in your own program, then there is also a static library in the ./bin folder.

Testing

kleuren uses the C++ unit-testing library catch to run unit tests. To run the test suite, you can execute ./bin/kleuren_test.

The data for the unit test is found in the test/data/small directory, and the unit tests themselves are found in test/src directory.

Using kleuren

kleuren depends on the BloomFilterTrie to represent the CdBG. Thus, one must create the BloomFilterTrie representation of the CdBG and pass that into kleuren. In order to create the CdBG one must count the kmers of the genomes and pass that into BloomFilterTrie.

There is a scipipe workflow available at kleuren-scipipe-workflow. This will install kleuren and all of the other dependencies needed (BloomFilterTrie and jellyfish) to run kleuren end-to-end, from genomes to bubbles. If you would like to just see the steps needed to create the necessary files, an example can be found in test/Makefile.

What's in a name?

Kleuren is the Dutch word for colors, which pays homage to the language of the home country of the de Bruin graph's namesake, Nicolaas Govert de Bruijn.

kleuren's Issues

git submodule update failing

I think it might be because the remote submodule repos are using git@guthub instead of http protocol (maybe?).

git submodule update --init --recursive

<snip>

Please make sure you have the correct access rights
and the repository exists.
fatal: clone of '[email protected]:Colelyman/dbgfm.git' into submodule path '/home/linuxbrew/tmp/kleuren/thirdparty/dbgfm' failed
Failed to clone 'thirdparty/dbgfm'. Retry scheduled
Cloning into '/home/linuxbrew/tmp/kleuren/thirdparty/doxygen-bootstrapped'...
Permission denied (publickey).
fatal: Could not read from remote repository.

Segmentation Fault- Driver::run() getting ColorSet

There is a segmentation fault early on in the program in Driver::run(). I think that the issue is with ColorManager::getColors(unsigned int n) because it seems that it is returning a faulty pointer to a Color.

Make a "pre release"

Cole,

I was hoping you would consider make another release version using the github "Releases" mechanism, with a version number of 1.1.0 or similar. I will then package it in Brew.

Torsten

Extending path with branching nodes

There is a problem with extending a path that is not linear, basically, if there is a node that branches then the path is not valid.

The problem is that the path is passed by reference, and it is not cleared when an invalid path is followed. Somehow the path needs to be cleared when an invalid path is followed.

Extending path with identical start and end kmer

Currently, the extendPath method will only return the startKmer when startKmer == endKmer. Is this the correct behavior should a bubble be able to be a loop?

I think that a bubble should be able to be a loop, because if the endKmer is the same as the startKmer, then there has to be a path that forms that loop. Furthermore, biologically a loop can suggest an indel in one species that is not present in others.

Stack overflow in `recursiveExtend` helper method

There is a stack overflowin the recursiveExtend method because the base case is not being hit. This results in a Bus error :(.