title: BRIDES: A New Fast Algorithm and Software for Characterizing Evolving Similarity Networks Using Breakthroughs, Roadblocks, Impasses, Detours, Equals and Shortcuts.
abstract: Various types of genome and gene similarity networks along with their characteristics have been increasingly used for retracing different kinds of evolutionary and ecological relationships. Here, we present a new polynomial time algorithm and the corresponding software (BRIDES) to provide characterization of different types of paths existing in evolving (or augmented) similarity networks under the constraint that such paths contain at least one node that was not present in the original network. These different paths are denoted as Breakthroughs, Roadblocks, Impasses, Detours, Equal paths, and Shortcuts. The analysis of their distribution can allow discriminating among different evolutionary hypotheses concerning genomes or genes at hand. Our approach is based on an original application of the popular shortest path Dijkstra's and Yen's algorithms. The C++ and R versions of the BRIDES program are freely available at: https://github.com/etiennelord/BRIDES.
authors: Département d'informatique, Université du Québec à Montréal, Montréal, Québec, Canada.|Département de sciences biologiques, Université de Montréal, Montréal, Québec, Canada.
authors: Etienne
authors: E
authors: Lord
authors: Département de sciences biologiques, Université de Montréal, Montréal, Québec, Canada.
authors: Margaux
authors: M
authors: Le Cam
authors: Sorbonne Universités, UPMC Université Paris 06, Institut de Biologie Paris-Seine, Paris, France.|CNRS, UMR7138, Institut de Biologie Paris-Seine, Paris, France.
authors: Éric
authors: É
authors: Bapteste
authors: Sorbonne Universités, UPMC Université Paris 06, Institut de Biologie Paris-Seine, Paris, France.
authors: Raphaël
authors: R
authors: Méheust
authors: Département d'informatique, Université du Québec à Montréal, Montréal, Québec, Canada.
authors: Vladimir
authors: V
authors: Makarenkov
authors: Département de sciences biologiques, Université de Montréal, Montréal, Québec, Canada.
authors: François-Joseph
authors: FJ
authors: Lapointe
mesh_terms: D000465:Algorithms; D019143:Evolution, Molecular; D053263:Gene Regulatory Networks / Q000502:physiology*; D016678:Genome / Q000502:physiology*; D017422:Sequence Analysis, DNA / Q000379:methods*; D012984:Software