The Gene-CluEDO package

[Tags:gpl, library, program, test]

Gene Cluster Evolution Determined Order

Calculate the most likely order of genes in a gene cluster.

Apart from being an interesting problem in computational biology, it also serves as an example problem for dynamic programming over unordered sets with interfaces.


[Skip to Readme]

Properties

Versions 0.0.0.1
Change log changelog.md
Dependencies ADPfusion (==0.5.2.*), ADPfusionSet (==0.0.0.*), base (>=4.7 && <5.0), cmdargs (>=0.10), containers, filepath, FormalGrammars (==0.3.1.*), Gene-CluEDO, log-domain (>=0.10), PrimitiveArray (==0.8.0.*), PrimitiveArray-Pretty (==0.0.0.*), ShortestPathProblems (==0.0.0.*), text (>=1.0), vector (>=0.11) [details]
License GPL-3
Copyright Christian Hoener zu Siederdissen, 2017
Author Christian Hoener zu Siederdissen, 2017
Maintainer choener@bioinf.uni-leipzig.de
Category Bioinformatics
Home page https://github.com/choener/Gene-CluEDO
Bug tracker https://github.com/choener/Gene-CluEDO/issues
Source repository head: git clone git://github.com/choener/Gene-CluEDO
Uploaded Fri Apr 7 10:29:27 UTC 2017 by ChristianHoener
Distributions NixOS:0.0.0.1
Downloads 66 total (11 in the last 30 days)
Votes
0 []
Status Docs available [build log]
Last success reported on 2017-04-07 [all 1 reports]
Hackage Matrix CI

Modules

[Index]

Downloads

Maintainer's Corner

For package maintainers and hackage trustees

Readme for Gene-CluEDO

Readme for Gene-CluEDO-0.0.0.1

Build Status

generalized Algebraic Dynamic Programming Homepage

Gene-CluEDO: Gene Cluster Evolution Determined Order

  1. Hoener zu Siederdissen, Christian and Prohaska, Sonja J. and Stadler, Peter F.
    Dynamic Programming for Set Data Types
    2014, Lecture Notes in Bioinformatics, 8826,
    preprint: http://www.bioinf.uni-leipzig.de/~choener/pdfs/hoe-pro-2014.pdf

  2. Hoener zu Siederdissen, Christian and Prohaska, Sonja J. and Stadler, Peter F.
    Algebraic Dynamic Programming over General Data Structures
    2015, BMC Bioinformatics
    oa: https://doi.org/10.1186/1471-2105-16-S19-S2

  3. Prohaska, Sonja J. and Berkemer, Sarah and Externbrink, Fabian and Gatter, Thomas
    and Retzlaff, Nancy and The Students of the Graphs and Biological Networks Lab 2017
    and H"oner zu Siederdissen, Christian and Stadler, Peter F.
    Expansion of Gene Clusters and the Shortest Hamiltonian Path Problem
    2017
    preprint: http://www.bioinf.uni-leipzig.de/~choener/pdfs/pro-ber-2017.pdf

This program accepts a matrix with distances between nodes (see below for an example). It then proceeds to calculate the Hamiltonian path with the shortest distance between each pair of nodes, where the path has to travel from the start, then to all other nodes, finally stopping at the last node.

We further calculate all neighbour probabilities via Inside/Outside. This means that for any two nodes we calculate the weight of the edge between these two nodes. The weight is between [0, ... ,1] where 0 denotes the the nodes are almost surely not direct neighbours on a weighted-randomly drawn path, while 1 denotes that they almost surely are.

Finally, we calculate the probability that a node is one of the terminal nodes in the Hamiltonian path, i.e. either the first or the last node.

The Biological Problem We Solve

Wikipedia on Hox clusters.

Hox clusters are a set of genes that are linearly ordered. The genes are (assumed) to have a single originating gene, and repeated duplication has led to the cluster with unknown duplication tree.

The long time scales involved make it hard to produce a tree that can be trusted. This program therefore produces summary information in the form of edge path probabilities.

Example matrix:

In this artificial distance matrix, we have prime numbers as distances between nodes. Store the matrix in a file, say mat.dat.

#   A   B   C   D   E
A   0   2   3   5   7
B   2   0  11  13  17
C   3  11   0  19  23
D   5  13  19   0  27
E   7  17  23  27   0

Now, run the algorithm ./GeneCluEDO -o output.run ./mat.dat. After the program has run, output.run contains the a wealth of information about the input. The maximum likelihood path, the edge weights, end probabilities, and maximum expected accuracy path are calculated. Two additional files, here output.boundary.svg, and output.edge.svg are produced. The boundary plot provides graphical output of the probability that a node (or gene) is the start or end node. The edge probability plot provides probabilities for each edge (i,j) between nodes. This shows the most likely neighbors, and therefore genetic relationship, over all possible gene orders.

Contact

Christian Hoener zu Siederdissen
Leipzig University, Leipzig, Germany
choener@bioinf.uni-leipzig.de
http://www.bioinf.uni-leipzig.de/~choener/