Shortcuts, Detours and Dead Ends (SDDE) Path Types in Genome Similarity Networks


SDDE compares the evolution of an original network X to an augmented network Y by counting the number of shortcuts, detours, dead ends, equal paths and disconnected nodes.

Four different types of paths in Y that pass by at least one augmented node (i.e. a node that exists in Y but not in X) can be defined as follows:

1) Shortcut is a path between two nodes, originally present in X, that is shorter in Y than in X.

2) Detour is a path such that it connects two nodes originally present in X and is longer in Y than in X.

3) Dead End is a path that exists in X, but is impossible in Y.

4) Equal is a path that has the same length in X an Y.

The numbers of disconnected nodes is also reported.


Package: SDDE
Type: Package
Version: 1.0.1
Date: 2015-08-20
License: GPL-2
Maintainer: Etienne Lord <>,
François-Joseph Lapointe <>

Function complete_network computes the number of paths in each category.

Function complete_restart is similar to the complete_network function but it identifies the paths in a predefined order.

Function complete_trace is similar to the complete_network function but allow the enumeration of nodes and taxa in a path.

Function sample_network computes the number of paths in each category for a given set of nodes of the original network X.

Function random_network creates a random network X and an augmented network Y using Erdos-Renyi or Barabási–Albert models.

Function save_network and codeplot_network creates rendering of network X and network Y in various file formats (svg, png and eps).

Function load_network loads a network from a list of edges (tab-separated) which is compatible with the complete_network, complete_restart and sample_network function.


Etienne Lord, Margaux Le Cam, Éric Bapteste, Vladimir Makarenkov and François-Joseph Lapointe

See Also

complete_network, complete_restart, complete_trace, sample_network, load_network, save_network plot_network

Want to suggest features or report bugs for Use the GitHub issue tracker. Vote for new features on Trello.

comments powered by Disqus