IDEAS home Printed from https://ideas.repec.org/a/plo/pone00/0161474.html
   My bibliography  Save this article

BRIDES: A New Fast Algorithm and Software for Characterizing Evolving Similarity Networks Using Breakthroughs, Roadblocks, Impasses, Detours, Equals and Shortcuts

Author

Listed:
  • Etienne Lord
  • Margaux Le Cam
  • Éric Bapteste
  • Raphaël Méheust
  • Vladimir Makarenkov
  • François-Joseph Lapointe

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.

Suggested Citation

  • Etienne Lord & Margaux Le Cam & Éric Bapteste & Raphaël Méheust & Vladimir Makarenkov & François-Joseph Lapointe, 2016. "BRIDES: A New Fast Algorithm and Software for Characterizing Evolving Similarity Networks Using Breakthroughs, Roadblocks, Impasses, Detours, Equals and Shortcuts," PLOS ONE, Public Library of Science, vol. 11(8), pages 1-13, August.
    • Handle: RePEc:plo:pone00:0161474
    DOI: 10.1371/journal.pone.0161474
    as

    Download full text from publisher

    File URL: https://journals.plos.org/plosone/article?id=10.1371/journal.pone.0161474
    Download Restriction: no
    File URL: https://journals.plos.org/plosone/article/file?id=10.1371/journal.pone.0161474&type=printable
    Download Restriction: no
    File URL: https://libkey.io/10.1371/journal.pone.0161474?utm_source=ideas
    LibKey link: if access is restricted and if your library uses this service, LibKey will redirect you to where you can use your library subscription to access this item
    ---><---

    References listed on IDEAS

    as
    1. Chiara Orsini & Marija M. Dankulov & Pol Colomer-de-Simón & Almerima Jamakovic & Priya Mahadevan & Amin Vahdat & Kevin E. Bassler & Zoltán Toroczkai & Marián Boguñá & Guido Caldarelli & Santo Fortunat, 2015. "Quantifying randomness in real networks," Nature Communications, Nature, vol. 6(1), pages 1-10, December.
    2. José M. Montoya & Stuart L. Pimm & Ricard V. Solé, 2006. "Ecological networks and their fragility," Nature, Nature, vol. 442(7100), pages 259-264, July.
    Full references (including those not matched with items on IDEAS)

    Most related items

    These are the items that most often cite the same works as this one and are cited by the same works as this one.
    1. Zechen Wang & Zhenqin Shi & Jingeng Huo & Wenbo Zhu & Yanhui Yan & Na Ding, 2023. "Construction and Optimization of an Ecological Network in Funiu Mountain Area Based on MSPA and MCR Models, China," Land, MDPI, vol. 12(8), pages 1-13, August.
    2. Xiaolong Lin & Zongmu Yao & Xinguang Wang & Shangqi Xu & Chunjie Tian & Lei Tian, 2021. "Water-Covered Depth with the Freeze–Thaw Cycle Influences Fungal Communities on Rice Straw Decomposition," Agriculture, MDPI, vol. 11(11), pages 1-16, November.
    3. Leto Peel & Tiago P. Peixoto & Manlio De Domenico, 2022. "Statistical inference links data and theory in network science," Nature Communications, Nature, vol. 13(1), pages 1-15, December.
    4. Dina in ‘t Zandt & Zuzana Kolaříková & Tomáš Cajthaml & Zuzana Münzbergová, 2023. "Plant community stability is associated with a decoupling of prokaryote and fungal soil networks," Nature Communications, Nature, vol. 14(1), pages 1-14, December.
    5. Bellingeri, Michele & Cassi, Davide & Vincenzi, Simone, 2013. "Increasing the extinction risk of highly connected species causes a sharp robust-to-fragile transition in empirical food webs," Ecological Modelling, Elsevier, vol. 251(C), pages 1-8.
    6. Zhang, Yan & Wu, Tong & Song, Changsu & Hein, Lars & Shi, Faqi & Han, Mingchen & Ouyang, Zhiyun, 2022. "Influences of climate change and land use change on the interactions of ecosystem services in China’s Xijiang River Basin," Ecosystem Services, Elsevier, vol. 58(C).
    7. Saucan, Emil & Sreejith, R.P. & Vivek-Ananth, R.P. & Jost, Jürgen & Samal, Areejit, 2019. "Discrete Ricci curvatures for directed networks," Chaos, Solitons & Fractals, Elsevier, vol. 118(C), pages 347-360.
    8. Wang, Jin-Liang & Wu, Huai-Ning, 2011. "Stability analysis of impulsive parabolic complex networks," Chaos, Solitons & Fractals, Elsevier, vol. 44(11), pages 1020-1034.
    9. Torres-Alruiz, Maria Daniela & Rodríguez, Diego J., 2013. "A topo-dynamical perspective to evaluate indirect interactions in trophic webs: New indexes," Ecological Modelling, Elsevier, vol. 250(C), pages 363-369.
    10. Shengnan Chen & Huiyan He & Rongrong Zong & Kaiwen Liu & Yutian Miao & Miaomiao Yan & Lei Xu, 2020. "Geographical Patterns of Algal Communities Associated with Different Urban Lakes in China," IJERPH, MDPI, vol. 17(3), pages 1-19, February.
    11. Yuxiang Zhao & Zishu Liu & Baofeng Zhang & Jingjie Cai & Xiangwu Yao & Meng Zhang & Ye Deng & Baolan Hu, 2023. "Inter-bacterial mutualism promoted by public goods in a system characterized by deterministic temperature variation," Nature Communications, Nature, vol. 14(1), pages 1-12, December.
    12. Hayato Goto & Hideki Takayasu & Misako Takayasu, 2017. "Estimating risk propagation between interacting firms on inter-firm complex network," PLOS ONE, Public Library of Science, vol. 12(10), pages 1-12, October.
    13. Robin Lamarche-Perrin & Sven Banisch & Eckehard Olbrich, 2016. "The Information Bottleneck Method For Optimal Prediction Of Multilevel Agent-Based Systems," Advances in Complex Systems (ACS), World Scientific Publishing Co. Pte. Ltd., vol. 19(01n02), pages 1-45, February.
    14. Marco Alberto Javarone & Daniele Marinazzo, 2018. "Dilution of Ferromagnets via a Random Graph-Based Strategy," Complexity, Hindawi, vol. 2018, pages 1-11, April.
    15. Canelas, Joana Viana & Pereira, Henrique Miguel, 2022. "Impacts of land-use intensity on ecosystems stability," Ecological Modelling, Elsevier, vol. 472(C).
    16. Gilboa-Freedman, Gail & Hassin, Refael, 2016. "When Markov chains meet: A continuous-time model of network evolution," Statistics & Probability Letters, Elsevier, vol. 116(C), pages 131-138.
    17. Zimo Yang & Tao Zhou & Pak Ming Hui & Jian-Hong Ke, 2012. "Instability in Evolutionary Games," PLOS ONE, Public Library of Science, vol. 7(11), pages 1-9, November.
    18. Qing Cai & Mahardhika Pratama & Sameer Alam, 2019. "Interdependency and Vulnerability of Multipartite Networks under Target Node Attacks," Complexity, Hindawi, vol. 2019, pages 1-16, November.
    19. Liang, Xinyuan & Jin, Xiaobin & He, Jie & Wang, Xiaorui & Xu, Cuilan & Qiao, Guoliang & Zhang, Xiaolin & Zhou, Yinkang, 2022. "Impacts of land management practice strategy on regional ecosystems: Enlightenment from ecological redline adjustment in Jiangsu, China," Land Use Policy, Elsevier, vol. 119(C).
    20. Savoca, S. & Grifó, G. & Panarello, G. & Albano, M. & Giacobbe, S. & Capillo, G. & Spanó, N. & Consolo, G., 2020. "Modelling prey-predator interactions in Messina beachrock pools," Ecological Modelling, Elsevier, vol. 434(C).

    More about this item

    Statistics

    Access and download statistics

    Corrections

    All material on this site has been provided by the respective publishers and authors. You can help correct errors and omissions. When requesting a correction, please mention this item's handle: RePEc:plo:pone00:0161474. See general information about how to correct material in RePEc.

    If you have authored this item and are not yet registered with RePEc, we encourage you to do it here. This allows to link your profile to this item. It also allows you to accept potential citations to this item that we are uncertain about.

    If CitEc recognized a bibliographic reference but did not link an item in RePEc to it, you can help with this form .

    If you know of missing items citing this one, you can help us creating those links by adding the relevant references in the same way as above, for each refering item. If you are a registered author of this item, you may also want to check the "citations" tab in your RePEc Author Service profile, as there may be some citations waiting for confirmation.

    For technical questions regarding this item, or to correct its authors, title, abstract, bibliographic or download information, contact: plosone (email available below). General contact details of provider: https://journals.plos.org/plosone/ .

    Please note that corrections may take a couple of weeks to filter through the various RePEc services.

    IDEAS is a RePEc service. RePEc uses bibliographic data supplied by the respective publishers.