東華大學圖書館 |

Language: English

Help

回圖書館首頁

手機版館藏查詢

Back

Switch To: Labeled | MARC Mode | ISBD

Multi-node graphs and their applicat...

Rachlin, John N.

Linked to FindBook

Google Book

Amazon

博客來

Multi-node graphs and their application to bioinformatics.

Record Type:	Electronic resources : Monograph/item
Title/Author:	Multi-node graphs and their application to bioinformatics./
Author:	Rachlin, John N.
Description:	147 p.
Notes:	Source: Dissertation Abstracts International, Volume: 68-03, Section: B, page: 1736.
Contained By:	Dissertation Abstracts International68-03B.
Subject:	Biology, Bioinformatics. -
Online resource:	http://pqdd.sinica.edu.tw/twdaoapp/servlet/advanced?query=3254472

Multi-node graphs and their application to bioinformatics.
Rachlin, John N.

Multi-node graphs and their application to bioinformatics. - 147 p.

Source: Dissertation Abstracts International, Volume: 68-03, Section: B, page: 1736.

Thesis (Ph.D.)--Boston University, 2007.

Graph and network models are fundamental to the theory and practice of computer science and operations research. In bioinformatics, they are the foundation for a wide-range of combinatorial optimization problems and also serve to model molecular interactions occurring inside the living cell. In this thesis we introduce a novel graph-theoretic framework called a multi-node graph and describe its application to optimization and modeling problems in bioinformatics. A multi-node graph denotes a graph whose vertices have multiple states or labels, and whose edges are active or inactive as a function of the current state of the incident vertices. We show that finding disjoint cliques in a multi-node graph is computationally equivalent to finding a valid multiplex PCR design, a widely used experimental protocol. Moreover, the multi-node graph model provides a theoretical and algorithmic framework for analyzing, for the first time, the protocol's scalability and limits. Our computational simulations using human DNA sequences reveal a phase transition where finding a valid assay design becomes suddenly more difficult as multiplexing targets are increased. This result has been subsequently confirmed by theoretical analysis on random multi-node graphs. To address the inherent computational challenges of designing highly multiplexed PCR assays, we developed a multi-objective assay design system based on an evolutionary computing framework. The system, known as "MuPlex", serves as a test-bed for developing novel design algorithms and has been employed by laboratories worldwide. We apply this optimization technology to design a SNP-based forensic assay for human identification, producing a design whose theoretical discriminating power exceeds existing forensic standards even in situations involving highly degraded DNA samples. We then show that a special case of a multi-node graph (termed a biological context network) can be used to analyze changing context-specific patterns of protein-protein interaction in the organism Saccharomyces cerevisiae. Here, context may refer to a specific biological process or cellular location. We find that proteins that have highly variable patterns of interaction from one context to another (termed 'interactively promiscuous') are significantly more likely to be essential to the viability of the organism, suggesting that biological context networks could aid in identifying putative drug targets.Subjects--Topical Terms:

1018415
Biology, Bioinformatics.

Multi-node graphs and their application to bioinformatics.
LDR:03286nmm 2200265 4500 001 1833880
005 20071114145436.5
008 130610s2007 eng d
035 $a (UMI)AAI3254472
035 $a AAI3254472
040 $a UMI $c UMI
100 1 $a Rachlin, John N. $3 1922561
245 1 0 $a Multi-node graphs and their application to bioinformatics.
300 $a 147 p.
500 $a Source: Dissertation Abstracts International, Volume: 68-03, Section: B, page: 1736.
500 $a Adviser: Simon Kasif.
502 $a Thesis (Ph.D.)--Boston University, 2007.
520 $a Graph and network models are fundamental to the theory and practice of computer science and operations research. In bioinformatics, they are the foundation for a wide-range of combinatorial optimization problems and also serve to model molecular interactions occurring inside the living cell. In this thesis we introduce a novel graph-theoretic framework called a multi-node graph and describe its application to optimization and modeling problems in bioinformatics. A multi-node graph denotes a graph whose vertices have multiple states or labels, and whose edges are active or inactive as a function of the current state of the incident vertices. We show that finding disjoint cliques in a multi-node graph is computationally equivalent to finding a valid multiplex PCR design, a widely used experimental protocol. Moreover, the multi-node graph model provides a theoretical and algorithmic framework for analyzing, for the first time, the protocol's scalability and limits. Our computational simulations using human DNA sequences reveal a phase transition where finding a valid assay design becomes suddenly more difficult as multiplexing targets are increased. This result has been subsequently confirmed by theoretical analysis on random multi-node graphs. To address the inherent computational challenges of designing highly multiplexed PCR assays, we developed a multi-objective assay design system based on an evolutionary computing framework. The system, known as "MuPlex", serves as a test-bed for developing novel design algorithms and has been employed by laboratories worldwide. We apply this optimization technology to design a SNP-based forensic assay for human identification, producing a design whose theoretical discriminating power exceeds existing forensic standards even in situations involving highly degraded DNA samples. We then show that a special case of a multi-node graph (termed a biological context network) can be used to analyze changing context-specific patterns of protein-protein interaction in the organism Saccharomyces cerevisiae. Here, context may refer to a specific biological process or cellular location. We find that proteins that have highly variable patterns of interaction from one context to another (termed 'interactively promiscuous') are significantly more likely to be essential to the viability of the organism, suggesting that biological context networks could aid in identifying putative drug targets.
590 $a School code: 0017.
650 4 $a Biology, Bioinformatics. $3 1018415
650 4 $a Computer Science. $3 626642
690 $a 0715
690 $a 0984
710 2 0 $a Boston University. $3 1017454
773 0 $t Dissertation Abstracts International $g 68-03B.
790 1 0 $a Kasif, Simon, $e advisor
790 $a 0017
791 $a Ph.D.
792 $a 2007
856 4 0 $u http://pqdd.sinica.edu.tw/twdaoapp/servlet/advanced?query=3254472