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.
展开▼
