Hundreds of Mathematics books at half price + FREE shipping! Get yours now >>

Atlantis Studies in Computing

Analysis and Enumeration

Algorithms for Biological Graphs

Authors: Marino, Andrea

  • Provides the reader with a systematic description of the main techniques to design enumeration algorithms
  • Fills a gap in the existing literature on enumeration algorithms in general and on biological enumeration algorithms especially
  • Gives the reader a detailed insight in four new examples of enumeration algorithms
see more benefits

Buy this book

eBook 59,49 €
price for Italia (gross)
  • ISBN 978-94-6239-097-3
  • Digitally watermarked, DRM-free
  • Included format: EPUB, PDF
  • ebooks can be used on all reading devices
  • Immediate eBook download after purchase
Hardcover 72,79 €
price for Italia (gross)
  • ISBN 978-94-6239-096-6
  • Free shipping for individuals worldwide
  • Usually dispatched within 3 to 5 business days.
About this book

In this work we plan to revise the main techniques for enumeration algorithms and to show four examples of enumeration algorithms that can be applied to efficiently deal with some biological problems modelled by using biological networks: enumerating central and peripheral nodes of a network, enumerating stories, enumerating paths or cycles, and enumerating bubbles. Notice that the corresponding computational problems we define are of more general interest and our results hold in the case of arbitrary graphs. Enumerating all the most and less central vertices in a network according to their eccentricity is an example of an enumeration problem whose solutions are polynomial and can be listed in polynomial time, very often in linear or almost linear time in practice. Enumerating stories, i.e. all maximal directed acyclic subgraphs of a graph G whose sources and targets belong to a predefined subset of the vertices, is on the other hand an example of an enumeration problem with an exponential number of solutions, that can be solved by using a non trivial brute-force approach. Given a metabolic network, each individual story should explain how some interesting metabolites are derived from some others through a chain of reactions, by keeping all alternative pathways between sources and targets. Enumerating cycles or paths in an undirected graph, such as a protein-protein interaction undirected network, is an example of an enumeration problem in which all the solutions can be listed through an optimal algorithm, i.e. the time required to list all the solutions is dominated by the time to read the graph plus the time required to print all of them. By extending this result to directed graphs, it would be possible to deal more efficiently with feedback loops and signed paths analysis in signed or interaction directed graphs, such as gene regulatory networks. Finally, enumerating mouths or bubbles with a source s in a directed graph, that is enumerating all the two vertex-disjoint directed paths between the source s and all the possible targets, is an example of an enumeration problem in which all the solutions can be listed through a linear delay algorithm, meaning that the delay between any two consecutive solutions is linear, by turning the problem into a constrained cycle enumeration problem. Such patterns, in a de Bruijn graph representation of the reads obtained by sequencing, are related to polymorphisms in DNA- or RNA-seq data.

Table of contents (8 chapters)

  • Introduction

    Marino, Andrea

    Pages 1-9

    Preview Buy Chapter 30,44 €
  • Enumeration Algorithms

    Marino, Andrea

    Pages 13-35

    Preview Buy Chapter 30,44 €
  • An Application: Biological Graph Analysis

    Marino, Andrea

    Pages 37-44

    Preview Buy Chapter 30,44 €
  • Telling Stories: Enumerating Maximal Directed Acyclic Graphs with Constrained Set of Sources and Targets

    Marino, Andrea

    Pages 47-63

    Preview Buy Chapter 30,44 €
  • Enumerating Bubbles: Listing Pairs of Vertex Disjoint Paths

    Marino, Andrea

    Pages 65-77

    Preview Buy Chapter 30,44 €

Buy this book

eBook 59,49 €
price for Italia (gross)
  • ISBN 978-94-6239-097-3
  • Digitally watermarked, DRM-free
  • Included format: EPUB, PDF
  • ebooks can be used on all reading devices
  • Immediate eBook download after purchase
Hardcover 72,79 €
price for Italia (gross)
  • ISBN 978-94-6239-096-6
  • Free shipping for individuals worldwide
  • Usually dispatched within 3 to 5 business days.
Loading...

Recommended for you

Loading...

Bibliographic Information

Bibliographic Information
Book Title
Analysis and Enumeration
Book Subtitle
Algorithms for Biological Graphs
Authors
Series Title
Atlantis Studies in Computing
Series Volume
6
Copyright
2015
Publisher
Atlantis Press
Copyright Holder
Atlantis Press and the authors
eBook ISBN
978-94-6239-097-3
DOI
10.2991/978-94-6239-097-3
Hardcover ISBN
978-94-6239-096-6
Series ISSN
2212-8557
Edition Number
1
Number of Pages
XVII, 151
Number of Illustrations and Tables
39 b/w illustrations
Topics