Analysis and Enumeration : Algorithms for Biological Graphs
Resource Information
The work Analysis and Enumeration : Algorithms for Biological Graphs represents a distinct intellectual or artistic creation found in Boston University Libraries. This resource is a combination of several types including: Work, Language Material, Books.
The Resource
Analysis and Enumeration : Algorithms for Biological Graphs
Resource Information
The work Analysis and Enumeration : Algorithms for Biological Graphs represents a distinct intellectual or artistic creation found in Boston University Libraries. This resource is a combination of several types including: Work, Language Material, Books.
 Label
 Analysis and Enumeration : Algorithms for Biological Graphs
 Title remainder
 Algorithms for Biological Graphs
 Statement of responsibility
 by Andrea Marino
 Subject

 Bioinformatics
 Computer science
 Computer science
 Bioinformatics
 Bioinformatics
 Computer software
 Algorithm Analysis and Problem Complexity
 Computer Science
 Computer Science
 Electronic resources
 Data mining
 Computer software
 Computer software
 Data Mining and Knowledge Discovery
 Data mining
 Computer Science
 Computational Biology/Bioinformatics
 Computer science
 Data mining
 Language
 eng
 Summary
 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 bruteforce 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 proteinprotein 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 vertexdisjoint 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 RNAseq data
 Image bit depth
 0
 LC call number
 QA76.9.A43
 Literary form
 non fiction
 Series statement
 Atlantis Studies in Computing,
 Series volume
 6
Context
Context of Analysis and Enumeration : Algorithms for Biological GraphsEmbed (Experimental)
Settings
Select options that apply then copy and paste the RDF/HTML data fragment to include in your application
Embed this data in a secure (HTTPS) page:
Layout options:
Include data citation:
<div class="citation" vocab="http://schema.org/"><i class="fa faexternallinksquare fafw"></i> Data from <span resource="http://link.bu.edu/resource/1rbofrdDXqk/" typeof="CreativeWork http://bibfra.me/vocab/lite/Work"><span property="name http://bibfra.me/vocab/lite/label"><a href="http://link.bu.edu/resource/1rbofrdDXqk/">Analysis and Enumeration : Algorithms for Biological Graphs</a></span>  <span property="potentialAction" typeOf="OrganizeAction"><span property="agent" typeof="LibrarySystem http://library.link/vocab/LibrarySystem" resource="http://link.bu.edu/"><span property="name http://bibfra.me/vocab/lite/label"><a property="url" href="http://link.bu.edu/">Boston University Libraries</a></span></span></span></span></div>
Note: Adjust the width and height settings defined in the RDF/HTML code fragment to best match your requirements
Preview
Cite Data  Experimental
Data Citation of the Work Analysis and Enumeration : Algorithms for Biological Graphs
Copy and paste the following RDF/HTML data fragment to cite this resource
<div class="citation" vocab="http://schema.org/"><i class="fa faexternallinksquare fafw"></i> Data from <span resource="http://link.bu.edu/resource/1rbofrdDXqk/" typeof="CreativeWork http://bibfra.me/vocab/lite/Work"><span property="name http://bibfra.me/vocab/lite/label"><a href="http://link.bu.edu/resource/1rbofrdDXqk/">Analysis and Enumeration : Algorithms for Biological Graphs</a></span>  <span property="potentialAction" typeOf="OrganizeAction"><span property="agent" typeof="LibrarySystem http://library.link/vocab/LibrarySystem" resource="http://link.bu.edu/"><span property="name http://bibfra.me/vocab/lite/label"><a property="url" href="http://link.bu.edu/">Boston University Libraries</a></span></span></span></span></div>