東華大學圖書館 |

語系: 繁體中文

說明(常見問題)

回圖書館首頁

手機版館藏查詢

登入

回首頁

切換: 標籤 | MARC模式 | ISBD

Multi-node graphs and their applicat...

Rachlin, John N.

FindBook

Google Book

Amazon

博客來

Multi-node graphs and their application to bioinformatics.

紀錄類型:	書目-電子資源 : Monograph/item
正題名/作者:	Multi-node graphs and their application to bioinformatics./
作者:	Rachlin, John N.
面頁冊數:	147 p.
附註:	Source: Dissertation Abstracts International, Volume: 68-03, Section: B, page: 1736.
Contained By:	Dissertation Abstracts International68-03B.
標題:	Biology, Bioinformatics. -
電子資源:	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