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. 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).
    6. 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.
    7. 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.
    8. 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.
    9. 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.
    10. 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).
    11. 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).
    12. Walter Leal Filho & Julian Hunt & Alexandros Lingos & Johannes Platje & Lara Werncke Vieira & Markus Will & Marius Dan Gavriletea, 2021. "The Unsustainable Use of Sand: Reporting on a Global Problem," Sustainability, MDPI, vol. 13(6), pages 1-16, March.
    13. Josep M. Antó & José Luis Martí & Jaume Casals & Paul Bou-Habib & Paula Casal & Marc Fleurbaey & Howard Frumkin & Manel Jiménez-Morales & Jacint Jordana & Carla Lancelotti & Humberto Llavador & Lela M, 2021. "The Planetary Wellbeing Initiative: Pursuing the Sustainable Development Goals in Higher Education," Sustainability, MDPI, vol. 13(6), pages 1-11, March.
    14. Liu, Jieyun & Qiu, Husen & He, Shuai & Tian, Guangli, 2024. "Long-term mulched drip irrigation facilitates soil organic carbon stabilization and the dominance of microbial stochastic assembly processes," Agricultural Water Management, Elsevier, vol. 302(C).
    15. Chengyi Tu & Joel Carr & Samir Suweis, 2016. "A data driven network approach to rank countries production diversity and food specialization," Papers 1606.01270, arXiv.org.
    16. Shuqi Qin & Dianye Zhang & Bin Wei & Yuanhe Yang, 2024. "Dual roles of microbes in mediating soil carbon dynamics in response to warming," Nature Communications, Nature, vol. 15(1), pages 1-11, December.
    17. Hsi-Cheng Ho & Jakob Brodersen & Martin M. Gossner & Catherine H. Graham & Silvana Kaeser & Merin Reji Chacko & Ole Seehausen & Niklaus E. Zimmermann & Loïc Pellissier & Florian Altermatt, 2022. "Blue and green food webs respond differently to elevation and land use," Nature Communications, Nature, vol. 13(1), pages 1-12, December.
    18. Yimin Li & Juanzhen Zhao & Jing Yuan & Peikun Ji & Xuanlun Deng & Yiming Yang, 2022. "Constructing the Ecological Security Pattern of Nujiang Prefecture Based on the Framework of “Importance–Sensitivity–Connectivity”," IJERPH, MDPI, vol. 19(17), pages 1-21, August.
    19. Enze Wang & Xiaolong Lin & Lei Tian & Xinguang Wang & Li Ji & Feng Jin & Chunjie Tian, 2021. "Effects of Short-Term Rice Straw Return on the Soil Microbial Community," Agriculture, MDPI, vol. 11(6), pages 1-15, June.
    20. Junya Wang & Yi-Jiao Zhang & Cong Xu & Jiaze Li & Jiachen Sun & Jiarong Xie & Ling Feng & Tianshou Zhou & Yanqing Hu, 2024. "Reconstructing the evolution history of networked complex systems," Nature Communications, Nature, vol. 15(1), pages 1-11, December.

    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.