Developing new ethical drugs is exceedingly expensive in terms of both time and resources. A single drug can take up to a decade to bring to market, with costs soaring to over a billion dollars. Drug repositioning has thus become an attractive alternative to the development of new compounds, with growing interest in the use of in silico repositioning predictions. Bipartite graphs and efficient biclique enumeration algorithms can be used to study drug-protein or other pairwise crucial interactions. Extensions of this approach to datasets with three or more divergent data types have been hobbled, however, by a lack of effective analytics. To address this shortcoming, a highly innovative and efficient graph theoretical technique is introduced to impute potential edges (links) in an arbitrary multipartite graph. The utility of this method is demonstrated on five tripartite graphs, each comprised of three partite sets, one each for diseases, drugs, and gene products of interest, and with interpartite edges denoting known interactions or associations. Evidence for the reliability of imputed edges is also reported.

In a large hospital system, a network of hospitals relies on electronic health records (EHRs) to make informed decisions regarding their patients in various clinical domains. Consequently, the dependability of the health information technology (HIT) systems responsible for collecting EHR data is of utmost importance for patient safety. Recently, novel methods and tools aimed at identifying anomalies in EHR data to bolster the reliability of HIT systems have been introduced. However, these existing methods and tools primarily concentrate on individual hospitals, which limits our understanding of system-wide anomalous events and their potential impact on patient safety across multiple hospitals. In this article, we introduce a new approach to detecting anomalies in EHR data within a network of hospitals. This is achieved by combining advanced machine learning techniques with graph algorithms to create a tool capable of swiftly identifying and responding to deviations. Our proposed approach employs a combination of five machine learning models, harnessing the unique strengths of each model to provide a more robust detection system. The detected anomalies are then represented as graphs, allowing us to recognize patterns across the hospital network. This aids in identifying anomalies that span multiple medical facilities, potentially indicating broader system-level risks. Extensive real-world testing of our approach demonstrated its ability to offer actionable insights compared to existing methods. Additionally, its scalable design ensures seamless integration into existing HIT infrastructures.

OBJECTIVE: Physicians and clinicians rely on data contained in electronic health records (EHRs), as recorded by health information technology (HIT), to make informed decisions about their patients. The reliability of HIT systems in this regard is critical to patient safety. Consequently, better tools are needed to monitor the performance of HIT systems for potential hazards that could compromise the collected EHRs, which in turn could affect patient safety. In this paper, we propose a new framework for detecting anomalies in EHRs using sequence of clinical events. This new framework, EHR-Bidirectional Encoder Representations from Transformers (BERT), is motivated by the gaps in the existing deep-learning related methods, including high false negatives, sub-optimal accuracy, higher computational cost, and the risk of information loss. EHR-BERT is an innovative framework rooted in the BERT architecture, meticulously tailored to navigate the hurdles in the contemporary BERT method; thus, enhancing anomaly detection in EHRs for healthcare applications. METHODS: The EHR-BERT framework was designed using the Sequential Masked Token Prediction (SMTP) method. This approach treats EHRs as natural language sentences and iteratively masks input tokens during both training and prediction stages. This method facilitates the learning of EHR sequence patterns in both directions for each event and identifies anomalies based on deviations from the normal execution models trained on EHR sequences. RESULTS: Extensive experiments on large EHR datasets across various medical domains demonstrate that EHR-BERT markedly improves upon existing models. It significantly reduces the number of false positives and enhances the detection rate, thus bolstering the reliability of anomaly detection in electronic health records. This improvement is attributed to the model's ability to minimize information loss and maximize data utilization effectively. CONCLUSION: EHR-BERT showcases immense potential in decreasing medical errors related to anomalous clinical events, positioning itself as an indispensable asset for enhancing patient safety and the overall standard of healthcare services. The framework effectively overcomes the drawbacks of earlier models, making it a promising solution for healthcare professionals to ensure the reliability and quality of health data.

Detecting anomalous sequences is an integral part of building and protecting modern large-scale health information technology (HIT) systems. These HIT systems generate a large volume of records of patients' state and significant events, which provide a valuable resource to help improve clinical decisions, patient care processes, and other issues. However, detecting anomalous sequences in electronic health records (EHR) remains a challenge in healthcare applications for several reasons, including imbalances in the data, complexity of relationships between events in the sequence, and the curse of dimensionality. Conventional anomaly detection methods use the finite sequence of events to discriminate sequences. They fail to incorporate salient event details under variable higher-order dependencies (e.g., duration between events) that can provide better discrimination of sequences in their models. To address this problem, we propose event sequence and subsequence anomaly detection algorithms that (1) use network-based representations of interactions in the data, (2) account for variable higher-order dependencies in the data, and (3) incorporate events duration for adequate discrimination of the data. The proposed approach identifies anomalies by monitoring the change in the graph after the test sequence is removed from the network. The change is quantified using graph distance metrics so that dramatic changes in the network can be attributed to the removed sequence. Furthermore, the proposed subsequence algorithm recommends plausible paths and salient information for the detected anomalous subsequences. Our results show that the proposed event sequence anomaly detection algorithm outperforms the baseline methods for both synthetic data and real-world EHR data.

Finding a minimum dominating set is a classic NP-hard problem from graph theory. Given a finite, simple, undirected graph, it seeks a smallest set of vertices with the property that every vertex in the graph is either in or adjacent to at least one member of that set. In recent years, it has found increased application, particularly when used as the basis for classifying nodes of biological networks. Sample networks include those derived from metabolic, noncoding RNA and protein-protein interaction data. Classification schemes employed to date, however, have typically been limited by the need to solve multiple problem instances, which naturally constrains the size of amenable networks. Moreover, analytical methods based on minimum dominating set have thus far generally been limited to static graphs. In this paper, work in progress is described that improves upon these algorithms and applies them to dynamic streaming graphs in order to capture control structures as they evolve over time. Results demonstrate the effectiveness of these techniques at reducing computational overhead. A systematic experimental setup and a description of testbed construction is also provided.

BACKGROUND: Cluster analysis is a core task in modern data-centric computation. Algorithmic choice is driven by factors such as data size and heterogeneity, the similarity measures employed, and the type of clusters sought. Familiarity and mere preference often play a significant role as well. Comparisons between clustering algorithms tend to focus on cluster quality. Such comparisons are complicated by the fact that algorithms often have multiple settings that can affect the clusters produced. Such a setting may represent, for example, a preset variable, a parameter of interest, or various sorts of initial assignments. A question of interest then is this: to what degree do the clusters produced vary as setting values change? RESULTS: This work introduces a new metric, termed simply "robustness", designed to answer that question. Robustness is an easily-interpretable measure of the propensity of a clustering algorithm to maintain output coherence over a range of settings. The robustness of eleven popular clustering algorithms is evaluated over some two dozen publicly available mRNA expression microarray datasets. Given their straightforwardness and predictability, hierarchical methods generally exhibited the highest robustness on most datasets. Of the more complex strategies, the paraclique algorithm yielded consistently higher robustness than other algorithms tested, approaching and even surpassing hierarchical methods on several datasets. Other techniques exhibited mixed robustness, with no clear distinction between them. CONCLUSIONS: Robustness provides a simple and intuitive measure of the stability and predictability of a clustering algorithm. It can be a useful tool to aid both in algorithm selection and in deciding how much effort to devote to parameter tuning.

This paper describes a framework combining graph theoretical tools and metrics with machine learning to analyze big geospatial data. By combining multiple methods targeted to different levels of resolution, this approach detects subtle normalcy patterns that would otherwise remain hidden to any single approach. Initial feasibility testing shows the applicability of the proposed methods to data from trip records of New York City taxis.

I1 Proceedings of the Fifteenth Annual UT- KBRIN Bioinformatics Summit 2016 Eric C. Rouchka, Julia H. Chariker, Benjamin J. Harrison, Juw Won Park P1 CC-PROMISE: Projection onto the Most Interesting Statistical Evidence (PROMISE) with Canonical Correlation to integrate gene expression and methylation data with multiple pharmacologic and clinical endpoints Xueyuan Cao, Stanley Pounds, Susana Raimondi, James Downing, Raul Ribeiro, Jeffery Rubnitz, Jatinder Lamba P2 Integration of microRNA-mRNA interaction networks with gene expression data to increase experimental power Bernie J Daigle, Jr. P3 Designing and writing software for in silico subtractive hybridization of large eukaryotic genomes Deborah Burgess, Stephanie Gehrlich, John C Carmen P4 Tracking the molecular evolution of Pax gene Nicholas Johnson; Chandrakanth Emani P5 Identifying genetic differences in thermally dimorphic and state specific fungi using in silico genomic comparison Stephanie Gehrlich, Deborah Burgess, John C Carmen P6 Identification of conserved genomic regions and variation therein amongst Cetartiodactyla species using next generation sequencing Kalpani De Silva, Michael P Heaton, Theodore S Kalbfleisch P7 Mining physiological data to identify patients with similar medical events and phenotypes Teeradache Viangteeravat, Rahul Mudunuri, Oluwaseun Ajayi, Fatih Şen, Eunice Y Huang P8 Smart brief for home health monitoring Mohammad Mohebbi, Luaire Florian, Douglas J Jackson, John F Naber P9 Side-effect term matching for computational adverse drug reaction predictions AKM Sabbir, Sally R Ellingson P10 Enrichment vs robustness: A comparison of transcriptomic data clustering metrics Yuping Lu, Charles A Phillips, Michael A Langston P11 Deep neural networks for transcriptome-based cancer classification Rahul K Sevakula, Raghuveer Thirukovalluru, Nishchal K. Verma, Yan Cui P12 Motif discovery using K-means clustering Mohammed Sayed, Juw Won Park P13 Large scale discovery of active enhancers from nascent RNA sequencing Jing Wang, Qi Liu, Yu Shyr P14 Computationally characterizing genomic pipelines and benchmarking results using GATK best practices on the high performance computing cluster at the University of Kentucky Xiaofei Zhang, Sally R Ellingson P15 Development of approaches enabling the identification of abnormal gene expression from RNA-Seq in personalized oncology Naresh Prodduturi, Gavin R Oliver, Diane Grill, Jie Na, Jeanette Eckel-Passow, Eric W Klee P16 Processing RNA-Seq data of plants infected with coffee ringspot virus Michael M Goodin, Mark Farman, Harrison Inocencio, Chanyong Jang, Jerzy W Jaromczyk, Neil Moore, Kelly Sovacool P17 Comparative transcriptomics of three Acinetobacter baumanii clinical isolates with different antibiotic resistance patterns Leon Dent, Mike Izban, Sammed Mandape, Shruti Sakhare, Siddharth Pratap, Dana Marshall P18 Metagenomic assessment of possible microbial contamination in the equine reference genome assembly M Scotty DePriest, James N MacLeod, Theodore S Kalbfleisch P19 Molecular evolution of cancer driver genes Chandrakanth Emani, Hanady Adam, Ethan Blandford, Joel Campbell, Joshua Castlen, Brittany Dixon, Ginger Gilbert, Aaron Hall, Philip Kreisle, Jessica Lasher, Bethany Oakes, Allison Speer, Maximilian Valentine P20 Biorepository Laboratory Information Management System Naga Satya V Rao Nagisetty, Rony Jose, Teeradache Viangteeravat, Robert Rooney, David Hains

Background Differential Shannon entropy (DSE) and differential coefficient of variation (DCV) have proven to be effective complements to differential expression (DE) in the analysis of gene co-expression data[1]. Because DSE and DCV measure difference in variability, rather than mere difference in magnitude, they can often identify significant changes in gene activity not reflected in mere mean expression level.

As the size of available data sets grows, so too does the demand for efficient parallel algorithms that will yield the solution to complex combinatorial problems on graphs that may be too large to fit entirely in memory. In previous work, we have provided a set of out-of-core algorithms to solve one of the central examples of such a problem, maximum clique. In this paper, we review the algorithms and report on our ongoing work to use them as a starting point for an optimized, highly scalable implementation of a maximum clique solver.

Materials and methods In this work, tripartite graphs are considered. Applications include comparing two sets of many gene-many disease associations. An algorithm is described that finds a maximum triclique in such a graph. It employs a branching strategy inspired by maximum clique algorithms for general graphs. A binary search tree is used, in which branch nodes in the tree represent vertices in the tripartite graph, and in which branching decisions are based on whether a vertex is in or out of a maximum triclique. A reduction rule is also introduced to filter out irrelevant vertices. This algorithm was developed in the context of GeneWeaver, an online system for the integration of functional genomics experimental results. In this system triclique extraction will enable fast transitive association of diseases based on the similarity of gene-disease associations from many experiments. Computational experience with huge volumes of experimental data is described.

BACKGROUND: Our knowledge of global protein-protein interaction (PPI) networks in complex organisms such as humans is hindered by technical limitations of current methods. RESULTS: On the basis of short co-occurring polypeptide regions, we developed a tool called MP-PIPE capable of predicting a global human PPI network within 3 months. With a recall of 23% at a precision of 82.1%, we predicted 172,132 putative PPIs. We demonstrate the usefulness of these predictions through a range of experiments. CONCLUSIONS: The speed and accuracy associated with MP-PIPE can make this a potential tool to study individual human PPI networks (from genomic sequences alone) for personalized medicine.

BACKGROUND: Integrating and analyzing heterogeneous genome-scale data is a huge algorithmic challenge for modern systems biology. Bipartite graphs can be useful for representing relationships across pairs of disparate data types, with the interpretation of these relationships accomplished through an enumeration of maximal bicliques. Most previously-known techniques are generally ill-suited to this foundational task, because they are relatively inefficient and without effective scaling. In this paper, a powerful new algorithm is described that produces all maximal bicliques in a bipartite graph. Unlike most previous approaches, the new method neither places undue restrictions on its input nor inflates the problem size. Efficiency is achieved through an innovative exploitation of bipartite graph structure, and through computational reductions that rapidly eliminate non-maximal candidates from the search space. An iterative selection of vertices for consideration based on non-decreasing common neighborhood sizes boosts efficiency and leads to more balanced recursion trees. RESULTS: The new technique is implemented and compared to previously published approaches from graph theory and data mining. Formal time and space bounds are derived. Experiments are performed on both random graphs and graphs constructed from functional genomics data. It is shown that the new method substantially outperforms the best previous alternatives. CONCLUSIONS: The new method is streamlined, efficient, and particularly well-suited to the study of huge and diverse biological data. A robust implementation has been incorporated into GeneWeaver, an online tool for integrating and analyzing functional genomics experiments, available at http://geneweaver.org. The enormous increase in scalability it provides empowers users to study complex and previously unassailable gene-set associations between genes and their biological functions in a hierarchical fashion and on a genome-wide scale. This practical computational resource is adaptable to almost any applications environment in which bipartite graphs can be used to model relationships between pairs of heterogeneous entities.

BACKGROUND: The maximum clique enumeration (MCE) problem asks that we identify all maximum cliques in a finite, simple graph. MCE is closely related to two other well-known and widely-studied problems: the maximum clique optimization problem, which asks us to determine the size of a largest clique, and the maximal clique enumeration problem, which asks that we compile a listing of all maximal cliques. Naturally, these three problems are NP-hard, given that they subsume the classic version of the NP-complete clique decision problem. MCE can be solved in principle with standard enumeration methods due to Bron, Kerbosch, Kose and others. Unfortunately, these techniques are ill-suited to graphs encountered in our applications. We must solve MCE on instances deeply seeded in data mining and computational biology, where high-throughput data capture often creates graphs of extreme size and density. MCE can also be solved in principle using more modern algorithms based in part on vertex cover and the theory of fixed-parameter tractability (FPT). While FPT is an improvement, these algorithms too can fail to scale sufficiently well as the sizes and densities of our datasets grow. RESULTS: An extensive testbed of benchmark graphs are created using publicly available transcriptomic datasets from the Gene Expression Omnibus (GEO). Empirical testing reveals crucial but latent features of such high-throughput biological data. In turn, it is shown that these features distinguish real data from random data intended to reproduce salient topological features. In particular, with real data there tends to be an unusually high degree of maximum clique overlap. Armed with this knowledge, novel decomposition strategies are tuned to the data and coupled with the best FPT MCE implementations. CONCLUSIONS: Several algorithmic improvements to MCE are made which progressively decrease the run time on graphs in the testbed. Frequently the final runtime improvement is several orders of magnitude. As a result, instances which were once prohibitively time-consuming to solve are brought into the domain of realistic feasibility.

BACKGROUND: A wealth of clustering algorithms has been applied to gene co-expression experiments. These algorithms cover a broad range of approaches, from conventional techniques such as k-means and hierarchical clustering, to graphical approaches such as k-clique communities, weighted gene co-expression networks (WGCNA) and paraclique. Comparison of these methods to evaluate their relative effectiveness provides guidance to algorithm selection, development and implementation. Most prior work on comparative clustering evaluation has focused on parametric methods. Graph theoretical methods are recent additions to the tool set for the global analysis and decomposition of microarray co-expression matrices that have not generally been included in earlier methodological comparisons. In the present study, a variety of parametric and graph theoretical clustering algorithms are compared using well-characterized transcriptomic data at a genome scale from Saccharomyces cerevisiae. METHODS: For each clustering method under study, a variety of parameters were tested. Jaccard similarity was used to measure each cluster's agreement with every GO and KEGG annotation set, and the highest Jaccard score was assigned to the cluster. Clusters were grouped into small, medium, and large bins, and the Jaccard score of the top five scoring clusters in each bin were averaged and reported as the best average top 5 (BAT5) score for the particular method. RESULTS: Clusters produced by each method were evaluated based upon the positive match to known pathways. This produces a readily interpretable ranking of the relative effectiveness of clustering on the genes. Methods were also tested to determine whether they were able to identify clusters consistent with those identified by other clustering methods. CONCLUSIONS: Validation of clusters against known gene classifications demonstrate that for this data, graph-based techniques outperform conventional clustering approaches, suggesting that further development and application of combinatorial strategies is warranted.

A d-dimensional Keller graph has vertices which are numbered with each of the 4d possible d-digit numbers (d-tuples) which have each digit equal to 0, 1, 2, or 3. Two vertices are adjacent if their labels differ in at least two positions, and in at least one position the difference in the labels is two modulo four. Keller graphs are in the benchmark set of clique problems from the DIMACS clique challenge, and they appear to be especially difficult for clique algorithms. The dimension seven case was the last remaining Keller graph for which the maximum clique order was not known. It has been claimed in order to resolve this last case it might take a “high speed computer the size of a major galaxy”. This paper describes the computation we used to determine that the maximum clique order for dimension seven is 124.

The Convex Recoloring (CR) problem measures how far a tree of characters differs from exhibiting a so-called “perfect phylogeny”. For an input consisting of a vertex-colored tree T, the problem is to determine whether recoloring at most k vertices can achieve a convex coloring, meaning by this a coloring where each color class induces a subtree. The problem was introduced by Moran and Snir (J. Comput. Syst. Sci. 73:1078–1089, 2007; J. Comput. Syst. Sci. 74:850–869, 2008) who showed that CR is NP-hard, and described a search-tree based FPT algorithm with a running time of O(k(k/log k) k n 4). The Moran and Snir result did not provide any nontrivial kernelization. In this paper, we show that CR has a kernel of size O(k 2).

Background Scientists are capable of performing very large scale gene expression experiments with current microarray technologies. In order to find significance in the expression data, it is common to use clustering algorithms to group genes with similar expression patterns. Clusters will often contain related genes, such as co-regulated genes or genes in the same biological pathway. It is too expensive and time consuming to test all of the relationships found in large scale microarray experiments. There are many bioinformatics tools that can be used to infer the significance of microarray experiments and cluster analysis.

Materials and methods We have developed a tool chain using novel graph algorithms to extract gene coexpression networks from microarray data. We highlight implementation of our tool chain to investigate the effects of in vivo low dose ionizing radiation treatments on mice. We are using systems genetics approach to investigate the biological effects of low dose (10 cGy) ionizing radiation. We measured the base line gene expression profile from spleen tissue of BXD recombinant inbred mice using Illumina microarrays. The data was filtered using coefficient of variance after robust spline normalization and variance stabilizing transformation. A graph was then derived from this data, with probes as vertices and edges between them representing correlations. The graph was analyzed using our toolkit to find the size and number of maximal cliques. We deployed another tool called paraclique that relaxes clique’s requirement that every edge be present between all vertices. Paraclique enables us to account for inherent noise in the microarray data and stochastic nature of biological processes. Using immunophenotype data from the baseline BXD mice, we employed biclique analysis to determine interactions between genotypes and immunophenotypes (%CD4, %CD3, LN T:B, %CD8, and LN CD4:CD8). We also extracted eQTLs from BXD data using QTL-Reaper from base line gene expression profiles. 1881 transcripts were associated with 686 loci. The eQTLs were classified as cis or trans according to their genomic positions. Besides population level studies we also investigated the differential effect of low dose and high dose (1Gy) of ionizing radiations on spleen gene expression in inbred parental strains (C57BL/6J and DBA/2J) of BXD recombinant inbred mice as well as BALB/c mice, a known radiation-sensitive strain.

Practical methods are presented for computing exact solutions to the maximum clique problem on graphs that are too large to fit within core memory. These methods use a combination of in-core and out-of-core techniques, recursively dissecting large graphs into manageable components. A global solution to the maximum clique problem is derived from local solutions generated for each of the individual components. Parallelizing the search within these components is instrumental in improving the running times of the algorithms.

BACKGROUND: Gene co-expression networks are often constructed by computing some measure of similarity between expression levels of gene transcripts and subsequently applying a high-pass filter to remove all but the most likely biologically-significant relationships. The selection of this expression threshold necessarily has a significant effect on any conclusions derived from the resulting network. Many approaches have been taken to choose an appropriate threshold, among them computing levels of statistical significance, accepting only the top one percent of relationships, and selecting an arbitrary expression cutoff. RESULTS: We apply spectral graph theory methods to develop a systematic method for threshold selection. Eigenvalues and eigenvectors are computed for a transformation of the adjacency matrix of the network constructed at various threshold values. From these, we use a basic spectral clustering method to examine the set of gene-gene relationships and select a threshold dependent upon the community structure of the data. This approach is applied to two well-studied microarray data sets from Homo sapiens and Saccharomyces cerevisiae. CONCLUSION: This method presents a systematic, data-based alternative to using more artificial cutoff values and results in a more conservative approach to threshold selection than some other popular techniques such as retaining only statistically-significant relationships or setting a cutoff to include a percentage of the highest correlations.

Parameterized complexity studies a generalization of the notion of polynomial time where, in addition to the overall input size n, one also considers the effects on computational complexity of a secondary measurement, the parameter. The central notion of the field is fixed-parameter tractability (FPT), which refers to solvability in time f(k)nc, where f is some function (usually exponential) of the parameter k, and c is a constant. The subject unfolds in two basic complementary projects and associated mathematical toolkits: (1) How to design (and improve) FPT algorithms, for parameterized problems that admit them and (2) How to gather evidence that a parameterized problem probably does not admit an FPT algorithm. There are several things that one can say about the field, in a general way. ... This Special Issue of surveys of various aspects of parameterized complexity and algorithmics began on the suggestion of the Editor-in-Chief, Fionn Murtagh, who after hearing a broad account of the field at a colloquium at Royal Holloway, University of London, declared, “This is a subject that every computer scientist should know about.”

Tools of molecular biology and the evolving tools of genomics can now be exploited to study the genetic regulatory mechanisms that control cellular responses to a wide variety of stimuli. These responses are highly complex, and involve many genes and gene products. The main objectives of this paper are to describe a novel research program centered on understanding these responses by i.developing powerful graph algorithms that exploit the innovative principles of fixed parameter tractability in order to generate distilled gene sets; ii.producing scalable, high performance parallel and distributed implementations of these algorithms utilizing cutting-edge computing platforms and auxiliary resources; iii.employing these implementations to identify gene sets suggestive of co-regulation; and iv.performing sequence analysis and genomic data mining to examine, winnow and highlight the most promising gene sets for more detailed investigation. As a case study, we describe our work aimed at elucidating genetic regulatory mechanisms that control cellular responses to low-dose ionizing radiation (IR). A low-dose exposure, as defined here, is an exposure of at most 10 cGy (rads). While the consequences of high doses of radiation are well known, the net outcome of low-dose exposures continues to be debated, with support in the literature for both detrimental and beneficialmore » effects. We use genome-scale gene expression data collected in response to low-dose IR exposure in vivo to identify the pathways that are activated or repressed as a tissue responds to the radiation insult. The driving motivation is that knowledge of these pathways will help clarify and interpret physiological responses to IR, which will advance our understanding of the health consequences of low-dose radiation exposures.« less

In the maximum common subgraph (MCS) problem, we are given a pair of graphs and asked to find the largest induced subgraph common to them both. With its plethora of applications, MCS is a familiar and challenging problem. Many algorithms exist that can deliver optimal MCS solutions, but whose asymptotic worst-case run times fail to do better than mere brute-force, which is exponential in the order of the smaller graph. In this paper, we present a faster solution to MCS. We transform an essential part of the search process into the task of enumerating maximal independent sets in only a part of only one of the input graphs. This is made possible by exploiting an efficient decomposition of a graph into a minimum vertex cover and the maximum independent set in its complement. The result is an algorithm whose run time is bounded by a function exponential in the order of the smaller cover rather than in the order of the smaller graph.

The analysis of proteome profiles offers a new approach to understanding how cellular machinery functions and responds under certain conditions. By combining two-dimensional electrophoresis with mass spectrometry (MS), a snapshot of the cell's protein expression status and quantitative proteome profiling can be provided. As the cell's proteome becomes defined in normal and altered states, possible utilization of MS proteome profiling as a diagnostic tool becomes a reality. The ability of Matrix Assisted Laser Desorption Ionization Mass Spectrometry (MALDI-MS) to generate a spectrum with thousands of data points, necessitate the development of sophisticated analytical algorithms. In this paper, we describe how MALDI-MS can be used in monitoring proteomic profile in patients before and after treatment using a non- invasive sampling method. Because data analysis in this process possesses a challenge, we present a novel mathematical approach for analyzing data produced by MALDI MS, and discuss current applications of mass spectrometry in clinical medicine as well as challenges faced during procedures and experimentation. As a case study, we analyze protein expression patterns in premenopausal versus postmenopausal women. We also provide a proteomic profiling of premenopausal women versus postmenopausal women treated with estrogen as a hormone replacement therapy. * Corresponding authors:

Genes with common functions often exhibit correlated expression levels, which can be used to identify sets of interacting genes from microarray data. Microarrays typically measure expression across genomic space, creating a massive matrix of co-expression that must be mined to extract only the most relevant gene interactions. We describe a graph theoretical approach to extracting co-expressed sets of genes, based on the computation of cliques. Unlike the results of traditional clustering algorithms, cliques are not disjoint and allow genes to be assigned to multiple sets of interacting partners, consistent with biological reality. A graph is created by thresholding the correlation matrix to include only the correlations most likely to signify functional relationships. Cliques computed from the graph correspond to sets of genes for which significant edges are present between all members of the set, representing potential members of common or interacting pathways. Clique membership can be used to infer function about poorly annotated genes, based on the known functions of better-annotated genes with which they share clique membership (i.e., "guilt-by-association"). We illustrate our method by applying it to microarray data collected from the spleens of mice exposed to low-dose ionizing radiation. Differential analysis is used to identify sets of genes whose interactions are impacted by radiation exposure. The correlation graph is also queried independently of clique to extract edges that are impacted by radiation. We present several examples of multiple gene interactions that are altered by radiation exposure and thus represent potential molecular pathways that mediate the radiation response.

Summary form only given. Two kernelization methods for the vertex cover problem are investigated. The first, LP-kernelization has been in prior use and is known to produce predictable results. The second, crown reduction, is newer and faster but generates more variable results. Previously-unknown connections between these powerful methods are established. It is also shown that the problem of finding an induced crown-free subgraph in an arbitrary graph is decidable in polynomial time. Applications of crown structures are discussed.

Graph-theoretical approaches to biological network analysis have proven to be effective for small networks but are computationally infeasible for comprehensive genome-scale systems-level elucidation of these networks. The difficulty lies in the NP-hard nature of many global systems biology problems that, in practice, translates to exponential (or worse) run times for finding exact optimal solutions. Moreover, these problems, especially those of an enumerative flavor, are often memory-intensive and must share very large sets of data effectively across many processors. For example, the enumeration of maximal cliques - a core component in gene expression networks analysis, cis regulatory motif finding, and the study of quantitative trait loci for high-throughput molecular phenotypes can result in as many as 3^n/3 maximal cliques for a graph with n vertices. Memory requirements to store those cliques reach terabyte scales even on modest-sized genomes. Emerging hardware architectures with ultra-large globally addressable memory such as the SGI Altix and Cray X1 seem to be well suited for addressing these types of data-intensive problems in systems biology. This paper presents a novel framework that provides exact, parallel and scalable solutions to various graph-theoretical approaches to genome-scale elucidation of biological networks. This framework takes advantage of these large-memory architectures by creating globally addressable bitmap memory indices with potentially high compression rates, fast bitwise-logical operations, and reduced search space. Augmented with recent theoretical advancements based on fixed-parameter tractability, this framework produces computationally feasible performance for genome-scale combinatorial problems of systems biology.

Summary form only given. We highlight a fruitful interplay between biology and computation. The sequencing of complete genomes from multiple organisms has revealed that most differences in organism complexity are due to elements of gene regulation that reside in the non protein coding portions of genes. Both within and between species, transcription factor binding sites and the proteins that recognize them govern the activity of cellular pathways that mediate adaptive responses and survival. Experimental identification of these regulatory elements is by nature a slow process. The availability of complete genomic sequences, however, opens the door for computational methods to predict binding sites and expedite our understanding of gene regulation at a genomic level. Just as with traditional experimental approaches, the computational identification of the molecular factors that control a gene's expression level has been problematic. As a case in point, the identification of putative motifs is a challenging combinatorial task. For it, powerful new motif finding algorithms and high performance implementations are described. Heavy use is made of graph algorithms, some of which are exceedingly computationally intensive and involve the use of emergent mathematical methods. An approach to fully dynamic load balancing is developed in order to make effective use of highly parallel platforms.

Graph width metrics have been widely studied for their relevance to VLSI design. Examples include cutwidth, pathwidth, bandwidth and several others that arise in circuit layout. When the width is bounded, graphs that satisfy these metrics can often be recognized by finite lists of obstruction tests. One of the most foundational tests is to determine whether K/sub 4/ is immersed in a graph. The authors present for the first time a fast, practical algorithm to perform this test, and discuss its relevance to cutwidth and other metrics.>

In an earlier research paper,9 we presented a novel, yet straightforward linear-time algorithm for merging two sorted lists in a fixed amount of additional space. Constant of proportionality estimates and empirical testing reveal that this procedure is reasonably competitive with merge routines free to squander unbounded additional memory, making it particularly attractive whenever space is a critical resource. In this paper, we devise a relatively simple strategy by which this efficient merge can be made stable, and extend our results in a nontrivial way to the problem of stable sorting by merging. We also derive upper bounds on our algorithms' constants of proportionality, suggesting that in some environments (most notably external file processing) their modest run-time premiums may be more than offset by the dramatic space savings achieved.

The existence of decision algorithms with low-degree polynomial running times for a number of well-studied graph layout, placement, and routing problems is nonconstructively proved. Some were not previously known to be in $\mathcal{P}$ at all; others were only known to be in $\mathcal{P}$ by way of brute force or dynamic programming formulations with unboundedly high-degree polynomial running times. The methods applied include the recent Robertson–Seymour theorems on the well-partial-ordering of graphs under both the minor and immersion orders. The complexity of search versions of these problems is also briefly addressed.

A report is presented on a collection of constructions of symmetric networks that provide the largest known values for the number of nodes that can be placed in a network of a given degree and diameter. Some of the constructions are in the range of current potential engineering significance. The constructions are Cayley graphs of linear groups obtained by experimental computation.>

The authors address the question 'when do three tracks suffice for the gate matrix layout of series-parallel circuits?' and demonstrate that the rather surprising answer appears to be 'almost always.' This is in contrast to the fact that an unbounded number of tracks may be required to layout contrived instances in the worst case. Their approach stems from the novel nonconstructive finite-basis characterization of graphs with k-track layouts for any fixed k.>

Consider the classic bin packing problem, in which we seek to pack a list of items into the minimum number of unit-capacity bins. The worst-case performance of a compound bin packing algorithm that selects the better packing produced by two previously analyzed heuristics, namely, FFD (first fit decreasing) and B2F (best two fit) is investigated. FFD and B2F can asymptotically require as many as $\frac{11}{9}$ and $\frac{5}{4}$ times the optimal number of bins, respectively. A new technique, weighting function averaging, is introduced to prove that our compound algorithm is superior to the individual heuristics on which it is based, never using more than $\frac{6}{5}$ times the optimal number of bins.

The authors present a parallel merging algorithm that, on an exclusive-read exclusive-write (EREW) parallel random-access machine (PRAM) with k processors merges two sorted lists of total length n in O(n/k+log n) time and constant extra space per processor, and hence is time-space optimal for any value of k>

A theorem that is a graph-theoretic analog of the Myhill-Nerode characterization of regular languages is proved. The theorem is used to establish that for many applications obstruction sets are computable by known algorithms. The focus is exclusively on what is computable (by a known algorithm) in principle, as opposed to what is computable in practice.>

Recent advances in well-partial-order theory, especially the seminal contributions of Robertson and Seymour, have troubling consequences for those who would equate tractability with polynomial-time decidability. Specifically:

The focus of this paper is on demonstrating the existence of methods for stably performing set and multiset operations on sorted files of data in both optimal time and optimal extra space. It is already known that stable merging and stable duplicate-key extraction permit such methods. The major new results reported herein are these

Recent advances in graph theory and graph algorithms dramatically alter the traditional view of concrete complexity theory, in which a decision problem is generally shown to be in P by producing an efficient algorithm to solve an optimization version of the problem. Nonconstructive tools are now available for classifying problems as decidable in polynomial time by guaranteeing only the existence of polynomial-time decision algorithms. In this paper these new methods are employed to prove membership in P for a number of problems whose complexities are not otherwise known. Powerful consequences of these techniques are pointed out and their utility is illustrated. A type of partially ordered set that supports this general approach is defined and explored.

The authors study the problem of assigning program fragments to a system of processing elements in which low-level operations are performed in parallel. Such a system is said to be linearly connected if each processing element can only communicate directly with its two nearest neighbors. They show that the problem of determining whether a perfect assignment exists is NP-complete but can be solved in linear time if the number of processing elements is fixed. They demonstrate that the related problem of determining whether any assignment exists which can be performed in a given number of machine cycles is NP-complete. For this problem, the objective of which corresponds to minimizing the program fragment's execution time, the authors also investigate the behavior of classes of near-optimal heuristic algorithms. This present evidence to indicate that guaranteeing acceptable worst-case performance is a very difficult problem as well.>

We consider the gate matrix layout problem for VLSI circuits, which is known to be NP-complete. We present an efficient algorithm for determining whether two tracks suffice. For the general problem of minimizing the number of tracks (and, hence, the area) needed, we design an attractive dynamic programming formulation to guarantee optimality. We also investigate the performance of fast heuristic algorithms published in the literature and demonstrate that there exist families of problem instances for which the ratio of the number of tracks required by these heuristics to the optimal value is unbounded. Moreover, we show that this result holds for any on-line layout algorithm. We additionally prove that, unless P = NP, no polynomial-time layout algorithm can ensure that the number of tracks it requires never exceeds k plus the optimum, for any constant k.

In the classical bin packing problem one seeks to pack a list of pieces in the minimum space using unit capacity bins. This paper addresses the more general problem in which a fixed collection of bin sizes is allowed. Three efficient approximation algorithms are described and analyzed. They guarantee asymptotic worst-case performance bounds of 2, ${3 / 2}$ and ${4 / 3}$.

We consider problems associated with the coordination of movement within a multiple robot system in which all motion is restricted to a single track. Our objective is to minimize the reconfiguration time, that is, the total time required to move a collection of robots from an initial to a goal configuration. We show that various models give rise to a wide range of problem complexities. For these problems we design and analyze optimization and approximation strategies.

We examine the nonpreemptive assignment of N independent tasks to a system of M uniform processors with the objective of reducing the makespan, or the time required from the start of execution until all tasks are completed. Since the problem of finding a minimal makespan has been shown to be NP-hard, and hence unlikely to permit an efficient solution procedure, near-optimal heuristic algorithms have been studied. It is known that LPT (longest processing time first) schedules are within twice the length of the optimum. We analyze a variation of the MULTIFIT algorithm derived from bin packing, and prove that its worst-case performance bound is within 1.4 of the optimum.