Borrow it
 Architecture Library
 Bizzell Memorial Library
 Boorstin Collection
 Chinese Literature Translation Archive
 Engineering Library
 Fine Arts Library
 Harry W. Bass Business History Collection
 History of Science Collections
 John and Mary Nichols Rare Books and Special Collections
 Library Service Center
 Price College Digital Library
 Western History Collections
The Resource Analysis and enumeration : algorithms for biological graphs, Andrea Marino
Analysis and enumeration : algorithms for biological graphs, Andrea Marino
Resource Information
The item Analysis and enumeration : algorithms for biological graphs, Andrea Marino represents a specific, individual, material embodiment of a distinct intellectual or artistic creation found in University of Oklahoma Libraries.This item is available to borrow from all library branches.
Resource Information
The item Analysis and enumeration : algorithms for biological graphs, Andrea Marino represents a specific, individual, material embodiment of a distinct intellectual or artistic creation found in University of Oklahoma Libraries.
This item is available to borrow from all library branches.
 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
 Language
 eng
 Extent
 1 online resource
 Contents

 Introduction
 Enumeration Algorithms
 An Application: Biological Graph Analysis
 Telling Stories: Enumerating maximal directed acyclic graphs with constrained set of sources and targets
 Enumerating bubbles: listing pairs of vertex disjoint paths
 Enumerating Cycles and (s, t)Paths in Undirected Graphs
 Enumerating Diametral and Radial vertices and computing Diameter and Radius of a graph
 Conclusions
 Isbn
 9789462390973
 Label
 Analysis and enumeration : algorithms for biological graphs
 Title
 Analysis and enumeration
 Title remainder
 algorithms for biological graphs
 Statement of responsibility
 Andrea Marino
 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
 Cataloging source
 N$T
 Dewey number
 570.151
 Illustrations
 illustrations
 Index
 no index present
 LC call number
 QH323.5
 LC item number
 .M37 2015eb
 Literary form
 non fiction
 Nature of contents

 dictionaries
 bibliography
 Series statement
 Atlantis studies in computing
 Series volume
 volume 6
 Label
 Analysis and enumeration : algorithms for biological graphs, Andrea Marino
 Antecedent source
 unknown
 Bibliography note
 Includes bibliographical references
 Carrier category
 online resource
 Carrier category code
 cr
 Carrier MARC source
 rdacarrier
 Color
 multicolored
 Content category
 text
 Content type code
 txt
 Content type MARC source
 rdacontent
 Contents
 Introduction  Enumeration Algorithms  An Application: Biological Graph Analysis  Telling Stories: Enumerating maximal directed acyclic graphs with constrained set of sources and targets  Enumerating bubbles: listing pairs of vertex disjoint paths  Enumerating Cycles and (s, t)Paths in Undirected Graphs  Enumerating Diametral and Radial vertices and computing Diameter and Radius of a graph  Conclusions
 Dimensions
 unknown
 Extent
 1 online resource
 File format
 unknown
 Form of item
 online
 Isbn
 9789462390973
 Level of compression
 unknown
 Media category
 computer
 Media MARC source
 rdamedia
 Media type code
 c
 Note
 SpringerLink
 Other control number
 10.2991/9789462390973
 Other physical details
 illustrations.
 Quality assurance targets
 not applicable
 Reformatting quality
 unknown
 Sound
 unknown sound
 Specific material designation
 remote
 System control number

 (OCoLC)905599929
 (OCoLC)ocn905599929
 Label
 Analysis and enumeration : algorithms for biological graphs, Andrea Marino
 Antecedent source
 unknown
 Bibliography note
 Includes bibliographical references
 Carrier category
 online resource
 Carrier category code
 cr
 Carrier MARC source
 rdacarrier
 Color
 multicolored
 Content category
 text
 Content type code
 txt
 Content type MARC source
 rdacontent
 Contents
 Introduction  Enumeration Algorithms  An Application: Biological Graph Analysis  Telling Stories: Enumerating maximal directed acyclic graphs with constrained set of sources and targets  Enumerating bubbles: listing pairs of vertex disjoint paths  Enumerating Cycles and (s, t)Paths in Undirected Graphs  Enumerating Diametral and Radial vertices and computing Diameter and Radius of a graph  Conclusions
 Dimensions
 unknown
 Extent
 1 online resource
 File format
 unknown
 Form of item
 online
 Isbn
 9789462390973
 Level of compression
 unknown
 Media category
 computer
 Media MARC source
 rdamedia
 Media type code
 c
 Note
 SpringerLink
 Other control number
 10.2991/9789462390973
 Other physical details
 illustrations.
 Quality assurance targets
 not applicable
 Reformatting quality
 unknown
 Sound
 unknown sound
 Specific material designation
 remote
 System control number

 (OCoLC)905599929
 (OCoLC)ocn905599929
Library Locations

Architecture LibraryBorrow itGould Hall 830 Van Vleet Oval Rm. 105, Norman, OK, 73019, US35.205706 97.445050



Chinese Literature Translation ArchiveBorrow it401 W. Brooks St., RM 414, Norman, OK, 73019, US35.207487 97.447906

Engineering LibraryBorrow itFelgar Hall 865 Asp Avenue, Rm. 222, Norman, OK, 73019, US35.205706 97.445050

Fine Arts LibraryBorrow itCatlett Music Center 500 West Boyd Street, Rm. 20, Norman, OK, 73019, US35.210371 97.448244

Harry W. Bass Business History CollectionBorrow it401 W. Brooks St., Rm. 521NW, Norman, OK, 73019, US35.207487 97.447906

History of Science CollectionsBorrow it401 W. Brooks St., Rm. 521NW, Norman, OK, 73019, US35.207487 97.447906

John and Mary Nichols Rare Books and Special CollectionsBorrow it401 W. Brooks St., Rm. 509NW, Norman, OK, 73019, US35.207487 97.447906


Price College Digital LibraryBorrow itAdams Hall 102 307 West Brooks St., Norman, OK, 73019, US35.210371 97.448244

Western History CollectionsBorrow itMonnet Hall 630 Parrington Oval, Rm. 300, Norman, OK, 73019, US35.209584 97.445414
Embed (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.libraries.ou.edu/portal/Analysisandenumerationalgorithmsfor/XJ06kvVPsZw/" typeof="Book http://bibfra.me/vocab/lite/Item"><span property="name http://bibfra.me/vocab/lite/label"><a href="http://link.libraries.ou.edu/portal/Analysisandenumerationalgorithmsfor/XJ06kvVPsZw/">Analysis and enumeration : algorithms for biological graphs, Andrea Marino</a></span>  <span property="potentialAction" typeOf="OrganizeAction"><span property="agent" typeof="LibrarySystem http://library.link/vocab/LibrarySystem" resource="http://link.libraries.ou.edu/"><span property="name http://bibfra.me/vocab/lite/label"><a property="url" href="http://link.libraries.ou.edu/">University of Oklahoma 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 Item Analysis and enumeration : algorithms for biological graphs, Andrea Marino
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.libraries.ou.edu/portal/Analysisandenumerationalgorithmsfor/XJ06kvVPsZw/" typeof="Book http://bibfra.me/vocab/lite/Item"><span property="name http://bibfra.me/vocab/lite/label"><a href="http://link.libraries.ou.edu/portal/Analysisandenumerationalgorithmsfor/XJ06kvVPsZw/">Analysis and enumeration : algorithms for biological graphs, Andrea Marino</a></span>  <span property="potentialAction" typeOf="OrganizeAction"><span property="agent" typeof="LibrarySystem http://library.link/vocab/LibrarySystem" resource="http://link.libraries.ou.edu/"><span property="name http://bibfra.me/vocab/lite/label"><a property="url" href="http://link.libraries.ou.edu/">University of Oklahoma Libraries</a></span></span></span></span></div>