Biological Network Analysis: Trends, Approaches, Graph Theory, and Algorithms

By Pietro Hiram Guzzi and Swarup Roy

Biological Network Analysis: Trends, Approaches, Graph Theory, and Algorithms considers three major biological networks, including Gene Regulatory Networks (GRN), Protein-Protein Interaction Networks (PPIN), and Human Brain Connectomes. The book's authors discuss various graph theoretic and data analytics approaches used to analyze these networks with respect to available tools, technologies, standards, algorithms and databases for generating, representing and analyzing graphical data. As a wide variety of algorithms have been developed to analyze and compare networks, this book is a timely resource.

• Presents recent advances in biological network analysis, combining Graph Theory, Graph Analysis, and various network models
• Discusses three major biological networks, including Gene Regulatory Networks (GRN), Protein-Protein Interaction Networks (PPIN) and Human Brain Connectomes
• Includes a discussion of various graph theoretic and data analytics approaches

• Language: English
• Publisher: Academic Press
• Release date: May 11, 2020
• ISBN: 9780128193518

Pietro Hiram Guzzi

Pietro Hiram Guzzi the Ph.D. degree in biomedical engi- neering from Magna Græcia University, Italy, in 2008. He has been an Associate Professor of computer engineering with Magna Græcia Univer- sity since 2008. He has been a Visiting Researcher with Georgia Tech University, Atlanta. He has authored two books. His research interests include semantic-based and network-based analysis of biological and clinical data. He is a member of the ACM, BITS, ISMB, and NETBIO COSI. He is an Editor of a newsletter of the ACM Special Interest Group on Bioinformatics, Computational Biology, and Biomedical Informatics (SIGBio), and the IEEE/ACM TRANSACTIONS ON COMPUTATIONAL BIOLOGY AND BIOINFORMATICS. He serves the scientific community as a reviewer for many conferenceS. He wrote two books and he edited another one.

Book preview

Biological Network Analysis

Trends, Approaches, Graph Theory, and Algorithms

First edition

Pietro Hiram Guzzi

University of Magna Græcia, Catanzaro, Italy

Swarup Roy

Sikkim (Central) University, Sikkim, India

Table of Contents

Cover image

Title page

Copyright

Dedication

Foreword

Preface

Acknowledgment

Abstract

1: Introduction

Abstract

1.1. What is a biological network?

1.2. Technologies for network data production

1.3. Network analysis models

1.4. Organization of the book

References

2: Preliminaries of graph theory

Abstract

2.1. Basic concepts

2.2. Data structure for representing graphs

2.3. Trees

2.4. Implementing graphs in R

2.5. Summary

References

3: Graph analysis

Abstract

Acknowledgement

3.1. Traversing a graph

3.2. Graph traversal at a glance

3.3. Shortest paths in a graph

3.4. Power graph analysis

3.5. Network centrality measures

3.6. Graph community and discovery

3.7. R scripts for graph analysis

3.8. Summary

References

4: Complex network models

Abstract

Acknowledgement

4.1. Complex graphs

4.2. Topological characteristics of networks

4.3. Network models

4.4. Graph modeling in R

4.5. Summary

References

5: Biological network databases

Abstract

5.1. No-SQL and graph databases

5.2. Genetic interaction network databases

5.3. Protein-protein network databases

5.4. Databases of brain networks

5.5. General purpose repository of networks

5.6. Summary

References

6: Gene expression networks: inference and analysis

Abstract

Acknowledgement

6.1. Expression network and analysis: the workflow

6.2. Basics of gene expression

6.3. Inference of expression networks

6.4. Inference assessment designs

6.5. Post inference network analysis

6.6. Network visualization and analysis tools

6.7. Summary

References

7: Protein interaction networks

Abstract

Acknowledgement

7.1. Proteins and interaction graph

7.2. Methods for protein interaction generation

7.3. Fitting protein networks into models

7.4. PPI network alignment for comparison

7.5. Protein networks complex detection

7.6. Summary

References

8: Brain connectome networks and analysis

Abstract

Acknowledgement

8.1. Human brain connectome

8.2. From neuroimaging to brain graph

8.3. Data storage and querying

8.4. Analysis of brain networks: tools and methodologies

8.5. Summary

References

9: Conclusion

Abstract

Index

Copyright

Elsevier

Radarweg 29, PO Box 211, 1000 AE Amsterdam, Netherlands

The Boulevard, Langford Lane, Kidlington, Oxford OX5 1GB, United Kingdom

50 Hampshire Street, 5th Floor, Cambridge, MA 02139, United States

Copyright © 2020 Elsevier Inc. All rights reserved.

No part of this publication may be reproduced or transmitted in any form or by any means, electronic or mechanical, including photocopying, recording, or any information storage and retrieval system, without permission in writing from the publisher. Details on how to seek permission, further information about the Publisher's permissions policies and our arrangements with organizations such as the Copyright Clearance Center and the Copyright Licensing Agency, can be found at our website: www.elsevier.com/permissions.

This book and the individual contributions contained in it are protected under copyright by the Publisher (other than as may be noted herein).

Notices

Knowledge and best practice in this field are constantly changing. As new research and experience broaden our understanding, changes in research methods, professional practices, or medical treatment may become necessary.

Practitioners and researchers must always rely on their own experience and knowledge in evaluating and using any information, methods, compounds, or experiments described herein. In using such information or methods they should be mindful of their own safety and the safety of others, including parties for whom they have a professional responsibility.

To the fullest extent of the law, neither the Publisher nor the authors, contributors, or editors, assume any liability for any injury and/or damage to persons or property as a matter of products liability, negligence or otherwise, or from any use or operation of any methods, products, instructions, or ideas contained in the material herein.

Library of Congress Cataloging-in-Publication Data

A catalog record for this book is available from the Library of Congress

British Library Cataloguing-in-Publication Data

A catalogue record for this book is available from the British Library

ISBN: 978-0-12-819350-1

For information on all Elsevier publications visit our website at https://www.elsevier.com/books-and-journals

Publisher: Mara Conner

Acquisitions Editor: Chris Katsaropoulos

Editorial Project Manager: Ana Claudia A. Garcia

Production Project Manager: Prasanna Kalyanaraman

Designer: Miles Hitchen

Typeset by VTeX

Dedication

To Anna, Fernando, Salvatore, Fernando Jr., and Pietro

—Pietro H. Guzzi

To Lt. Sukumar Roy (father), Lt. Subhash C Karmakar (father-in-law), and other members of my loving family (Dida, Maa, Mother-in-law, Chumki, Arpita, Srinika, and Shaunak)

—Swarup Roy

Foreword

Graph or network has become a powerful representation tool to specify relationships among data, and the graph theory has established a fundamental vehicle to mathematically model the pairwise relationship among different objects or entities. Consequently, graph has been popularly used to model various data from many applications. In biology, biological systems are composed of basic building blocks made up of mutually interacting cellular components. For example, it has been observed that proteins seldom act as single isolated species in the performance of their functions; rather, proteins involved in the same cellular processes often interact with each other. Such interaction relationships can be well modeled by a graph or network structure. Generally speaking, graph-based biological networks have become a novel mathematical tool to model the complex association among various cellular components, such as genes, proteins, and metabolites. It is also important to model them mathematically and computationally to derive a sketch on the interdependent relationships among the cellular components to elucidate such unknown rhythmic activities within a cell.

This book offers a comprehensive reading on biological network analysis. It includes fundamental and in-depth introductory materials on graph and graph theory. The book then demonstrates how the graph is applied to analyze various different types of biological networks. In particular, this book focuses on three types of biological networks: gene expression network, protein-protein interaction network, and brain connectome network. In-depth details are provided in separate chapters for each kind of the network, their properties, the process of generating them, and recent trends and tools in analyzing those networks. The discussion can be easily applied to other kind of networks, such as genetic network, DNA-protein network, signaling network, metabolic network, food web networks, neuronal networks, species interaction network, etc. The book also provides a chapter dedicated to the discussion of sources of biological network repositories in publicly available databases, which includes a basic introduction to popular and recently used database formats. It can be used as a resourceful reference for the biological network-related researchers.

I am fortunate to be one of the first few readers of the book, and I am excited to recommend it to the researchers who work on biological network analysis. The book is designed to be self-contained, as it includes introductions to the fundamental concepts underlying the graph and graph theory. It can be used as a textbook for advanced graduate courses in bioinformatics. In addition, the book can serve as a resource for graduate students seeking topics in the field of biological network analysis. It can also be used as an excellent reference book for research professionals, who are interested in expanding their knowledge in this topic.

Aidong Zhang

Fellow of ACM and IEEE

Professor of Computer Science

Professor of Biomedical Engineering

University of Virginia, Charlottesville, VA, United States

Preface

Pietro H. Guzzi; Swarup Roy     

The use of graph formalism enables the effective representation of the real-life entities and the complex and mutual interrelationships among the entities. Recently, the use of graphs has become a popular alternative in representing real complex systems, such as social networks, WWW, internet, airline citation, food web, economics, and most importantly, biological networks. Graph modeling of a large class of biological data and systems is growing. The importance of modeling the relationships relates to the consideration that all the biological systems (from the molecular scale to complex organs) are composed of a large set of small components that are strictly interconnected. Therefore, the use of graphs or networks is crucial in current science.

When we started working in the network analysis domain, we strongly realized the need for a good book, covering introductory and advanced topics in biological network analysis. This motivated us to write a handbook that may offer researchers, practitioners, and students a comprehensive guide towards main models, algorithms, and tools available in this area. This book aims to be a vade mecum in this field. While writing this book we tried our best to keep the book suitable for noncomputer science readers too. In it we discuss various graph theoretic and data analytics approaches in practice to analyze networks with respect to tools, technologies, standards, algorithms, and databases available for generating, representing, and analyzing graph data. We referred to recent researches in biological network analysis that might help the budding researchers.

We considered three major biological networks, including gene regulatory networks (GRN), protein-protein interaction networks (PPIN), and human brain connectomes. Keeping in mind the noncomputing readers, we started our discussion with the introductory graph theoretic concepts, which constitute the basis to understand the real-life networks. Real networks are termed as complex, due to their unconventional and nontrivial topological properties. We discussed the properties of complex network applicable to real networks. To start empirical study and analysis of various biological networks (that we covered), the sources of various publicly available input networks play an important role. We introduced such sources and the basic details of database and data storage formats. In most chapters, we demonstrated the use of programmes to implement graphs and its analysis using one of the powerful, freely available scripting languages, R.

We believe that this book will be a good starting study material for any research student planning to work in network analysis, and in particular, biological network analysis. To keep the book at a moderate size, we limit discussions on current methodologies and algorithms in use. We encourage interested readers to read original works for more details.

Acknowledgment

Pietro H. Guzzi     

Swarup Roy     

The authors would like to express deep gratitude to those who were directly and indirectly involved in the writing of this book.

We are grateful to Elsevier, USA for considering the project worthy for publication. Special thanks to Chris Katsaropoulos, Ana Claudia A. Garcia, Kalyanaraman, Prasanna, and their team for translating the dream into reality through the process of proposal finalization, tracking the progress, and final production. It would never be possible to complete the project without their active support and help.

We are thankful to our collaborators: Prof. Jugal Kalita (University of Colorado at CS), Prof. Mario Cannataro, and Prof. Pierangelo Veltri (University of Catanzaro), Prof. Dhruba K. Bhattacharyya (Tezpur University), Dr. Keshab Nath (NIT, Shillong), Dr. Ahed Elmsallati (McKendree University), Dr. Monica Jha (SMIT, Sikkim), Dr. Sazzad Ahmed (Assam Don-Bosco University), Ms. Hazel N. Manners and Mr. Gracious Kharumnuid (NEHU, Shillong), Mr. Partha P. Ray, Sk. Atahar Ali and Ms. Softya Sebastian (Sikkim University), and all the members of the Bioinformatics Lab of the University of Catanzaro for their direct and indirect collaboration and support for writing various chapters. Few of the chapters are the outcomes of various researches conducted with their collaboration during the last few decades.

Few significant experiments on network analysis, reported in this book, were conducted at the network reconstruction and analysis (NetRA) lab, Department of Computer Applications, Sikkim University, India. We are thankful to all the members of the NetRA Lab.

We are thankful to the University of Catanzaro (Italy) and Sikkim University (India) for providing us infrastructure facilities in the University premises for conducting biological network analysis researches. We acknowledge the fund received from the Department of Science and Technology (DST), Govt. of India under DST/ICPS/ Cluster /Data Science/2018 to set-up the NetRA lab and conducting various biological network inference and analysis researches.

While writing the book we referred to a number of related works in this area of research. We hereby acknowledge all the authors, whose research works have been reported in this book.

Last but not the least, we are grateful to the Almighty for everything. We are grateful to our loving family members for their constant support and encouragement. It would never be possible to complete the project successfully without their love and encouragement.

Readers are the most important part of any book. We are grateful to all anonymous readers who consider this book worth reading. Our effort will be successful if it motivates and helps readers in understanding the basics and trends in biological network researches.

Abstract

Complex biological systems and their interrelationships are often represented as a graph or network. Therefore, the use of graphs to model biological aspects in computational biology, in bioinformatics, and biomedicine is currently growing, since graphs enable researchers to model relations easily among objects. A main research in this area is represented by the inference and analysis of biological networks from experimental data. Often researchers aim to analyze differences of evolutions among different networks, i.e., network representing different states of the same reality, or networks coming from different species. Consequently a lot of algorithms to analyze and compare networks, have been developed. In particular, the comparison of networks is often performed through network alignment algorithms that rely on graph and subgraph isomorphisms. The book considers three major biological networks, namely, gene regulatory networks (GRN), protein-protein interaction networks (PPIN), and human brain connectomes, and discusses various graph theoretic and data analytics approaches adopted within the last few decades to analyze them with respect to tools, technologies, standards, algorithms, and databases available for generating, representing, analyzing graph data.

1

Introduction

Abstract

In a cell, the outcomes of any cellular activities are not the influence of any particular constituent. Instead, it is a rhythmic and collective role of multiple chemical components inside the cell. It is important to model them mathematically and computationally to derive a sketch on interdependency relationship among the cellular components to elucidate such unknown rhythmic activities within a cell. Biological networks are the graphical and mathematical modeling of such interactions or relationships. Graph theory models mathematically and computationally the pairwise relationship among different objects or entities. For this obvious reason, graph theory is considered as the best alternative for the formalism of biological network modeling and analysis. Many networks can be considered for describing various biological systems. Protein network, genetic network, DNA-protein network, signaling network, metabolic network, food web networks, neuronal networks, species interaction network, etc., are few biological networks commonly used for the study. We introduce the biological network, how to capture and model them for analysis, in this chapter.

Chapter Outline

1.1  What is a biological network?

1.2  Technologies for network data production

1.3  Network analysis models

1.4  Organization of the book

References

... I can't be as confident about computer science as I can about biology. Biology easily has 500 years of exciting problems to work on. It's at that level.

Donald E. Knuth (1993)

Biology deals with the science of life, whereas computer science models facts into a form that can be dealt with using the help of electronic computing devices. In truth, they are opposite in their actions. Even then, they are brought together to help biologists in handling biological data analysis. Biological experiments are slow and expensive. On the other hand, a computer can handle or process computational problems in less time, and cost-wise, it is less expensive.

In a cell, the outcomes of any cellular activities are not the influence of any particular constituent. Instead, it is a rhythmic and collective role of multiple chemical components inside the cell. It is important to model them mathematically and computationally to derive a sketch on interdependency relationships among the cellular components to elucidate such unknown rhythmic activities within a cell. Biological networks are the graphical and mathematical representation of such interactions or relationships. Graph theory is a mathematical tool that models the pairwise relationships among different objects or entities for the effective analysis. For this obvious reason, graph theory is considered as the best alternative for the formalism of biological network modeling and analysis. Many networks can be considered for describing various biological systems. Protein networks, genetic networks, DNA-protein networks, signaling networks, metabolic networks, food web networks, neuronal networks, species interaction network, etc., are few biological networks commonly used for the study. We introduce the biological network, how to capture and model them for analysis, next.

1.1 What is a biological network?

Biological systems are composed of little building blocks made up of mutually interacting [3] cellular components. The complex association among various cellular components, such as genes, proteins, metabolites, or even neuronal cells inside brains, is often modeled mathematically as a graph known as biological network. The comprehension of such systems is therefore related to the individuation of such elements and their relations. Bioinformatics and systems biology concentrates more on modeling the association among biological molecules on a system-level to improve the knowledge in molecular biology [8]. This approach of knowledge acquisition on a system scale relies on two main pillars: (i) the technological progress leading to the introduction of novel techniques capable of easy, quick, and reliable data generation, and (ii) the development of innovative methodological approaches to apply on the generated data to elucidate novel biological insights. Fig. 1.1 depicts this workflow.

Figure 1.1 Dataflow. The comprehension of biological systems starts with in vitro experiments performed in a wet lab. Here, a novel technological platform enables the (high)-throughput production of data related to cell mechanisms. Raw data are then stored in (public) databases. A set of models and algorithms are employed to model and analyze these data.

1.2 Technologies for network data production

The first pillar produces a lot of experimental data to gain insight into the properties of the systems, their properties, and