東華大學圖書館 |

Language: English

Help

回圖書館首頁

手機版館藏查詢

Back

Switch To: Labeled | MARC Mode | ISBD

Analysis and enumeration = algorithm...

Marino, Andrea.

Linked to FindBook

Google Book

Amazon

博客來

Analysis and enumeration = algorithms for biological graphs /

Record Type:	Electronic resources : Monograph/item
Title/Author:	Analysis and enumeration/ by Andrea Marino.
Reminder of title:	algorithms for biological graphs /
Author:	Marino, Andrea.
Published:	Paris :Atlantis Press : : 2015.,
Description:	xvii, 151 p. :ill., digital ;24 cm.
[NT 15003449]:	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.
Contained By:	Springer eBooks
Subject:	Biomathematics. -
Online resource:	http://dx.doi.org/10.2991/978-94-6239-097-3
ISBN:	9789462390973 (electronic bk.)

Analysis and enumeration = algorithms for biological graphs /
Marino, Andrea.

Analysis and enumerationalgorithms for biological graphs /[electronic resource] :by Andrea Marino. - Paris :Atlantis Press :2015. - xvii, 151 p. :ill., digital ;24 cm. - Atlantis studies in computing,v.62212-8557 ;. - Atlantis studies in computing ;v.1..

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.

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 RNN-seq data.

ISBN: 9789462390973 (electronic bk.)

Standard No.: 10.2991/978-94-6239-097-3doiSubjects--Topical Terms:

523796
Biomathematics.

LC Class. No.: QH323.5

Dewey Class. No.: 570.151

Analysis and enumeration = algorithms for biological graphs /
LDR:03920nmm a2200325 a 4500 001 1998093
003 DE-He213
005 20151029110923.0
006 m d
007 cr nn 008maaau
008 151112s2015 fr s 0 eng d
020 $a 9789462390973 (electronic bk.)
020 $a 9789462390966 (paper)
024 7 $a 10.2991/978-94-6239-097-3 $2 doi
035 $a 978-94-6239-097-3
040 $a GP $c GP
041 0 $a eng
050 4 $a QH323.5
072 7 $a UMB $2 bicssc
072 7 $a COM0513005570.151 |2 2370.151 |2 23 $2 bisacsh
082 0 4 $a 570.151 $2 23
090 $a QH323.5 $b .M339 2015
100 1 $a Marino, Andrea. $3 2139608
245 1 0 $a Analysis and enumeration $h [electronic resource] : $b algorithms for biological graphs / $c by Andrea Marino.
260 $a Paris : $b Atlantis Press : $b Imprint: Atlantis Press, $c 2015.
300 $a xvii, 151 p. : $b ill., digital ; $c 24 cm.
490 1 $a Atlantis studies in computing, $x 2212-8557 ; $v v.6
505 0 $a 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.
520 $a 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 RNN-seq data.
650 0 $a Biomathematics. $3 523796
650 0 $a Biology $x Mathematical models. $3 524939
650 1 4 $a Computer Science. $3 626642
650 2 4 $a Algorithm Analysis and Problem Complexity. $3 891007
650 2 4 $a Data Mining and Knowledge Discovery. $3 898250
650 2 4 $a Computational Biology/Bioinformatics. $3 898313
710 2 $a SpringerLink (Online service) $3 836513
773 0 $t Springer eBooks
830 0 $a Atlantis studies in computing ; $v v.1. $3 1619569
856 4 0 $u http://dx.doi.org/10.2991/978-94-6239-097-3
950 $a Mathematics and Statistics (Springer-11649)