SUPBUB is a tool that, in linear time, finds out superbubbles(special graph-structures) in a directed graph.
Switch branches/tags
Clone or download
Fetching latest commit…
Cannot retrieve the latest commit at this time.
Permalink
Type Name Latest commit message Commit time
Failed to load latest commit information.
data
result
.gitignore
.gitmodules
CandidateList.cpp
CandidateList.hpp
DAG.cpp
DAG.hpp
DetectSuperBubble.cpp
DetectSuperBubble.hpp
DevelopersNotes.md
Graph.cpp
Graph.hpp
INSTALL
LICENSE
Makefile
Makefile.32-bit.gcc
README.md
Subgraph.cpp
Subgraph.hpp
globalDefs.hpp
helper.cpp
helperDefs.hpp
pre-install.sh
supbub.cpp

README.md

SUPBUB : SuperBubbles

SUPBUB is a tool that finds out superbubbles in a directed graph. Detection method in a DAG is based on the algorithm described in the paper titled Linear-time superbubble identification algorithm by Ljiljana Brankovic, Costas S. Iliopoulos, Ritu Kundu, Manal Mohamed, Solon P. Pissis, Fatima Vayani

To compile SUPBUB, please follow the instructions given in file INSTALL.

To have an overview of the code-organisation, please read DevelopersNotes.md.

NOTE: When publishing work that is based on the results from Superbubble please cite:

L. Brankovic, C. S. Iliopoulos, R. Kundu, M. Mohamed, S. P. Pissis, F. Vayani, "Linear-Time Superbubble Identification Algorithm for Genome Assembly", Theoretical Computer Science, 2015.

Usage of the tool: supbub with the following options:

  • -i, --input-file Input file name.
  • -o, --output-file Output filename.

Example: ./supbub -i ./data/sample.txt -o ./result/sampleOutput.txt

Here, the edges of the graph are given in file "sample.txt" which is in subfolder "data" of current folder. SuperBubble will be calculated and result will be written in the file "sampleOutput.txt" in subfolder "result" of current folder.

** Notes **

  • Vertices are assumed to be zero-based integers.
  • Input file format required:
  • First line gives an inetger representing the number of vertices in the graph. Every line afterwards represents an edge.
  • Edges are delimited by new line, i.e. one edge on a single line.
  • An edge (say u->v) is represented by two numbers(corresponding to vertices u and v) separated by a space or a tab.
  • For example, a graph with say three vertices and three edges 0->1, 0->2, 1->2 will be required in the following format:
3
0 1
0 2
1 2
  • Output file is in the following format:
  • It writes the number of vertices and number of edges.
  • It also gives the time used for calculation (after input file has been read in memory and before writing the results).
  • After that, it indicates the number of superbubbles found.
  • Then it writes the superbubbles found in the following format:
  • <u, v> where u is entrance vertex of the superbubble and v is the exit vertex.
  • For answering rmq queries, following libraries have been used:
  • Solon's MAW helped as an inspiration for better organization of the code.