Coverart for item
The Resource Analysis and enumeration : algorithms for biological graphs, Andrea Marino

Analysis and enumeration : algorithms for biological graphs, Andrea Marino

Label
Analysis and enumeration : algorithms for biological graphs
Title
Analysis and enumeration
Title remainder
algorithms for biological graphs
Statement of responsibility
Andrea Marino
Creator
Author
Subject
Genre
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 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
Member of
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
Link
https://ezproxy.lib.ou.edu/login?url=http://link.springer.com/10.2991/978-94-6239-097-3
Instantiates
Publication
Copyright
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/978-94-6239-097-3
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
Link
https://ezproxy.lib.ou.edu/login?url=http://link.springer.com/10.2991/978-94-6239-097-3
Publication
Copyright
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/978-94-6239-097-3
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 it
    Gould Hall 830 Van Vleet Oval Rm. 105, Norman, OK, 73019, US
    35.205706 -97.445050
  • Bizzell Memorial LibraryBorrow it
    401 W. Brooks St., Norman, OK, 73019, US
    35.207487 -97.447906
  • Boorstin CollectionBorrow it
    401 W. Brooks St., Norman, OK, 73019, US
    35.207487 -97.447906
  • Chinese Literature Translation ArchiveBorrow it
    401 W. Brooks St., RM 414, Norman, OK, 73019, US
    35.207487 -97.447906
  • Engineering LibraryBorrow it
    Felgar Hall 865 Asp Avenue, Rm. 222, Norman, OK, 73019, US
    35.205706 -97.445050
  • Fine Arts LibraryBorrow it
    Catlett Music Center 500 West Boyd Street, Rm. 20, Norman, OK, 73019, US
    35.210371 -97.448244
  • Harry W. Bass Business History CollectionBorrow it
    401 W. Brooks St., Rm. 521NW, Norman, OK, 73019, US
    35.207487 -97.447906
  • History of Science CollectionsBorrow it
    401 W. Brooks St., Rm. 521NW, Norman, OK, 73019, US
    35.207487 -97.447906
  • John and Mary Nichols Rare Books and Special CollectionsBorrow it
    401 W. Brooks St., Rm. 509NW, Norman, OK, 73019, US
    35.207487 -97.447906
  • Library Service CenterBorrow it
    2601 Technology Place, Norman, OK, 73019, US
    35.185561 -97.398361
  • Price College Digital LibraryBorrow it
    Adams Hall 102 307 West Brooks St., Norman, OK, 73019, US
    35.210371 -97.448244
  • Western History CollectionsBorrow it
    Monnet Hall 630 Parrington Oval, Rm. 300, Norman, OK, 73019, US
    35.209584 -97.445414
Processing Feedback ...