Precision medicine requires drug repurposing methods that adapt to individual patient profiles while working within regulatory frameworks. Existing approaches apply uniform models to all patients, only using individual factors as inputs or filters. Our framework instead integrates patient-specific profiles into the learning algorithm through a customized loss function. We combine standard link prediction with UK Biobank data—integrating polygenic risk scores, biomarker expressions, and medical history. Evaluated on a biomedical knowledge graph connecting 61,000+ entities through 1.2+ million relations, our approach improves drug repurposing quality with AUPRC improvements ranging from 1.3 × to 5.4 × across patients. Case studies on Alzheimer’s Disease patients reveal drug candidates with stronger AD evidence and patient-specific mechanisms. Our loss function identifies influential diseases and biomarkers for each patient, enhancing interpretability while providing biologically relevant recommendations tailored to individual profiles. This approach represents a fundamental shift from treating personalization as data preprocessing to embedding it within the learning objective itself. • Algorithm-level personalization. We embed patient context directly into the learning objective via a patient-specific loss that blends standard link prediction with terms guided by polygenic risk scores (PRS) and protein-biomarker deviations, optimizing for an individual rather than the population. • Clinically grounded signals. We integrate UK Biobank–derived PRS, protein biomarker levels, and diagnosis history to tailor drug–disease scores to each patient’s biology and clinical context, anchoring personalization in routinely collectable, real-world data. • Preserved generalization with better rankings. We maintain foundation-model link-prediction quality while substantially improving patient-specific drug repurposing performance (e.g., AUPRC improvements ranging from 1.3 × to 5.4 × across patients), demonstrating effectiveness without sacrificing global metrics. • Interpretability at the patient level. We learn sparse, patient-level weights over diseases and biomarkers that reveal which comorbidities and dysregulated proteins drive recommendations, supporting transparent, clinician-facing interpretation.

Tabular data generation has attracted significant research interest in recent years, with the tabular diffusion models greatly improving the quality of synthetic data. However, while memorization—where models inadvertently replicate exact or near-identical training data—has been thoroughly investigated in image and text generation, its effects on tabular data remain largely unexplored. In this paper, we conduct the first comprehensive investigation of memorization phenomena in diffusion models for tabular data. Our empirical analysis reveals that memorization appears in tabular diffusion models and increases with larger training epochs. We further examine the influence of factors such as dataset sizes, feature dimensions, and different diffusion models on memorization. Additionally, we provide a theoretical explanation for why memorization occurs in tabular diffusion models. To address this issue, we propose TabCutMix, a simple yet effective data augmentation technique that exchanges randomly selected feature segments between random same-class training sample pairs. Building upon this, we introduce TabCutMixPlus, an enhanced method that clusters features based on feature correlations and ensures that features within the same cluster are exchanged together during augmentation. This clustering mechanism mitigates out-of-distribution (OOD) generation issues by maintaining feature coherence. Experimental results across various datasets and diffusion models demonstrate that TabCutMix effectively mitigates memorization while maintaining high-quality data generation. Our code is available at https://github.com/fangzy96/TabCutMix.

Recommender systems often involve multi-aspect factors. For example, when shopping for shoes online, consumers usually look through their images, ratings, and product's reviews before making their decisions. To learn multi-aspect factors, many context-aware models have been developed based on tensor factorizations. However, existing models assume multilinear structures in the tensor data, thus failing to capture nonlinear feature interactions. To fill this gap, we propose a novel nonlinear tensor machine, which combines deep neural networks and tensor algebra to capture nonlinear interactions among multi-aspect factors. We further consider adversarial learning to assist the training of our model. Extensive experiments demonstrate the effectiveness of the proposed model.

Precise medicine recommendations provide more effective treatments and cause fewer drug side effects. A key step is to understand the mechanistic relationships among drugs, targets, and diseases. Tensor-based models have the ability to explore relationships of drug-target-disease based on large amount of labeled data. However, existing tensor models fail to capture complex nonlinear dependencies among tensor data. In addition, rich medical knowledge are far less studied, which may lead to unsatisfied results. Here we propose a Neural Tensor Network (NeurTN) to assist personalized medicine treatments. NeurTN seamlessly combines tensor algebra and deep neural networks, which offers a more powerful way to capture the nonlinear relationships among drugs, targets, and diseases. To leverage medical knowledge, we augment NeurTN with geometric neural networks to capture the structural information of both drugs’ chemical structures and targets’ sequences. Extensive experiments on real-world datasets demonstrate the effectiveness of the NeurTN model.

Computational drug repositioning and drug-target prediction have become essential tasks in the early stage of drug discovery. In previous studies, these two tasks have often been considered separately. However, the entities studied in these two tasks (i.e., drugs, targets, and diseases) are inherently related. On one hand, drugs interact with targets in cells to modulate target activities, which in turn alter biological pathways to promote healthy functions and to treat diseases. On the other hand, both drug repositioning and drug-target prediction involve the same drug feature space, which naturally connects these two problems and the two domains (diseases and targets). By using the wisdom of the crowds, it is possible to transfer knowledge from one of the domains to the other. The existence of relationships among drug-target-disease motivates us to jointly consider drug repositioning and drug-target prediction in drug discovery. In this paper, we present a novel approach called iDrug, which seamlessly integrates drug repositioning and drug-target prediction into one coherent model via cross-network embedding. In particular, we provide a principled way to transfer knowledge from these two domains and to enhance prediction performance for both tasks. Using real-world datasets, we demonstrate that iDrug achieves superior performance on both learning tasks compared to several state-of-the-art approaches. Our code and datasets are available at: https://github.com/Case-esaC/iDrug.

Clustering is one of the most prominent topics in machine learning. A multitude of clustering methods have been proposed, among which the spectral clustering has attracted much attention. However, in practice, spectral clustering is highly sensitive to noise data and a post-processing step (e.g., k-means for eigenvectors) is often required to obtain clustering indicators, which may be not optimal. Also, it does not scale well to large-scale data due to its eigen-decomposition procedures.Here we propose a structure-aware clustering model to address those issues. To achieve our goal, a high-quality affinity matrix is extracted from the original noisy data by a sparse additive decomposition, which is used to approximate the ideal clustering structure. We then jointly learn the high-quality affinity matrix as well as the spectral embedding in a unified model- thus, being robust to noise and obtaining the optimal clustering indicators without any post-processing steps. We further improve the clustering stability by considering the Laplacian eigengap of the affinity matrix. We show that the larger the Laplacian eigengap, the more stable the clustering results. We introduce a speedup strategy to effectively compute eigenvectors of large matrices. Experimental results demonstrate that the proposed model outperforms existing approaches for noisy data.

Tag and item recommendation are both important tasks in recommender systems. Item recommendation, learning user-item rating patterns, helps users to discover a list of items that are more likely to match their interests. On the other hand, tag recommendation, exploiting relationships of user-tag-item, assists users to find a personalized list of tags that can precisely describe their experience on items. Existing methods often consider these two tasks independently. However, these two tasks are inherently related because they both use information from same groups of users and items. In other words, it is the same users who give ratings and annotate tags to the same set of items. Tags may explain why a user purchase an item. For instance, customers on Yelp not only give a five star rating for a restaurant but also leave comments/tags to express their positive sentiments. Users with similar interests might give similar ratings and post similar tags to certain items. The co-occurrence of users, items and tags motivates us to jointly perform item and tag recommendation to better model users' behavior by leveraging their personalized items and tags. In this work, we propose a cross-domain learning method that seamlessly integrates tag and item recommendation into one unified framework. In particular, we utilize the knowledge transferred between two tasks to collaboratively rank items and tags for users through coupled tensor-matrix factorization. We also provide a principled way to incorporate additional auxiliary information about users (e.g., users' relationships in a social network) and items (e.g., descriptions of items in Wikipedia) to improve recommendation accuracy for both tasks. Empirical results demonstrate the effectiveness of our proposed model.

Tensor completion has been successfully applied to many real-world applications. In a wide variety of situations, data utilized in many learning tasks are of high dimensions, usually extracted from multiple heterogeneous sources. Therefore, data can be represented by a primary tensor and multiple matrices generated from multi-view side information or metadata. Joint analysis of tensors and matrices has great potential to gain better understanding of the underlying relationships among these multiple heterogeneous sources. The existing tensor completion methods, which recover the missing elements of a partially known tensor with single view side information, can yield interpretable results for large-scale datasets. However, their limitations up to now are lack of modeling multi-view heterogeneous data and suitably learning the low-rank property of tensor. In this study, we fill this gap by developing a novel collective tensor completion method, which tightly fuses multi-view heterogeneous data sources. Our method exploits special common latent structures from the primary tensor and multiple side matrices through coupled tensor-matrix decomposition, in which the common latent structures can compactly represent all the data. In addition, rank estimation of a tensor is a challenging task due to its discrete nature. Instead of approximating the rank by widely used trace norm or nuclear norm, we directly utilize Schatten p-norm on the latent structures to better approximate the rank and to enhance its robustness to noise.

Cross-domain recommendation has attracted growing interests given their simplicity and effectiveness. In the cross-domain scenarios, we may improve predictive accuracy in one domain by transferring knowledge from the other, which alleviates the data sparsity issue. However, the relatedness of these domains can be exploited by a malicious party to launch data poisoning attacks. Here we study the vulnerability of cross-domain recommendation under data poisoning attacks. We show that data poisoning attacks can be formulated as a bilevel optimization problem. Our experimental results show that cross-domain system can be compromised under attacks, highlighting the need for countermeasures against data poisoning attacks in cross-domain recommendation.

Contextual factors such as time, location, or tag, can affect user preferences for a particular item. Context-aware recommendations are thus critical to improve both quality and explainability of recommender systems, compared to traditional recommendations that are solely based on user-item interactions. Tensor factorization machines have achieved the state-of-the-art performance due to their capability of integrating users, items, and contextual factors in one unify way. However, few work has focused on the robustness of a context-aware recommender system. Improving the robustness of a tensor-based model is challenging due to the sparsity of the observed tensor and the multi-linear nature of tensor factorization. In this paper, we propose ATF, a model that combines tensor factorization and adversarial learning for context-aware recommendations. Doing so allows us to reap the benefits of tensor factorization, while enhancing the robustness of a recommender model, and thus improves its eventual performance. Empirical studies on two real-world datasets show that the proposed method outperforms standard tensor-based methods.

Modeling the behaviors of drug-target-disease interactions is crucial in the early stage of drug discovery and holds great promise for precision medicine and personalized treatments. The growing availability of new types of data on the internet brings great opportunity of learning a more comprehensive relationship among drugs, targets, and diseases. However, existing methods often consider drug-target interactions or drug-disease interactions separately, which ignores the dependencies among these three entities. Also, many of them cannot directly incorporate rich heterogeneous information from diverse sources.

Link prediction in dynamic networks is an important task with many real-life applications in different domains, such as social networks, cyber-physical systems, and bioinformatics. There are two key processes in dynamic networks: network structural evolution and network temporal evolution, where the former represents interdependency between entities and their neighbors in the network at each timestamp, while the latter captures the evolving behavior of the entire network from the current timestamp to the next. Structural evolution generally assumes that a node is more likely to co-evolve with its neighbors in the near future. Temporal evolution focuses on the trend of network evolution as a whole, based on the accumulation of historical data. It is thus essential to use characteristics of both structural and temporal evolutions to emulate complex behaviors of dynamic networks. However, very few existing work considered both processes. In addition, real-life networks are often very sparse with limited observed links. A missing link between two nodes does not always imply that the two nodes do not have a relation in reality, especially when they share many common neighbors. Most existing methods only focus on the first-order proximity of networks, which is usually insufficient to capture the relationships among nodes.

Personalized treatments and targeted therapies are the most promising approaches to treat complex diseases, especially for cancer. However, drug resistance is often acquired after treatments. To overcome or reduce drug resistance, treatments using drug combinations have been actively investigated in the literature. Existing methods mainly focus on chemical properties of drugs for potential combination therapies without considering relationships among different diseases. Also, they often do not consider the rich knowledge of drugs and diseases, which can enhance the prediction of drug combinations. This motivates us to develop a new computational method that can predict the beneficial drug combinations. We propose DrugCom, a tensor-based framework for computing drug combinations across different diseases by integrating multiple heterogeneous data sources of drugs and diseases. DrugCom first constructs a primary third-order tensor (i.e., drug×drug ×disease) and several similarity matrices from multiple data sources regarding drugs (e.g., chemical structure) and diseases (e.g., disease phenotype). DrugCom then formulates an objective function, which simultaneously factorizes coupled tensor and matrices to reveal the molecular mechanisms of drug synergy. We adopt the alternating direction method of multipliers algorithm to effectively solve the optimization problem. Extensive experimental studies using real-world datasets demonstrate superior performance of DrugCom.

In addition to the sparse user-item (U-I) matrix, an increasing number of current recommender systems seek to improve performance by exploiting extra heterogeneous data sources (e.g., online social networks). Such rich side sources can provide very useful information about users' personal behaviors and items' properties, therefore can significantly benefit recommender systems. Most existing work can only incorporate a single side source of users or items. In many real-life applications, however, there exist multiple side sources for both users and items, which may be constructed from multiple domains. To incorporate multiple sources, we propose a flexible and robust algorithm called MSUI (Learning Multiple Similarities of Users and Items). The key idea of MSUI is to simultaneously capture the associations between latent factors in the U-I matrix and multiple side sources of users and items through joint nonnegative matrix factorization. MSUI has several advantages over existing methods. First, it seamlessly integrates information from the U-I matrix and information from multiple side sources. Second, by incorporating multiple sources that are usually in complementary, it's more robust to noise contained in each source. Finally, it provides a unified framework that can be easily extended to incorporate additional data sources.

BACKGROUND: Bisulfite sequencing is one of the most widely used technologies in analyzing DNA methylation patterns, which are important in understanding and characterizing the mechanism of DNA methylation and its functions in disease development. Efficient and user-friendly tools are critical in carrying out such analysis on high-throughput bisulfite sequencing data. However, existing tools are either not scalable well, or inadequate in providing visualization and other desirable functionalities. RESULTS: In order to handle ultra large sequencing data and to provide additional functions and features, we have developed BSPAT, a fast online tool for bisulfite sequencing pattern analysis. With a user-friendly web interface, BSPAT seamlessly integrates read mapping/quality control/methylation calling with methylation pattern generation and visualization. BSPAT has the following important features: 1) instead of using multiple/pairwise sequence alignment methods, BSPAT adopts an efficient and widely used sequence mapping tool to provide fast alignment of sequence reads; 2) BSPAT summarizes and visualizes DNA methylation co-occurrence patterns at a single nucleotide level, which provide valuable information in understanding the mechanism and regulation of DNA methylation; 3) based on methylation co-occurrence patterns, BSPAT can automatically detect potential allele-specific methylation (ASM) patterns, which can greatly enhance the detection and analysis of ASM patterns; 4) by linking directly with other popular databases and tools, BSPAT allows users to perform integrative analysis of methylation patterns with other genomic features together within regions of interest. CONCLUSION: By utilizing a real bisulfite sequencing dataset generated from prostate cancer cell lines, we have shown that BSPAT is highly efficient. It has also reported some interesting methylation co-occurrence patterns and a potential allele-specific methylation case. In conclusion, BSPAT is an efficient and convenient tool for high-throughput bisulfite sequencing data analysis that can be broadly used.

Given a large network, local community detection aims at finding the community that contains a set of query nodes and also maximizes (minimizes) a goodness metric. This problem has recently drawn intense research interest. Various goodness metrics have been proposed. However, most existing metrics tend to include irrelevant subgraphs in the detected local community. We refer to such irrelevant subgraphs as free riders. We systematically study the existing goodness metrics and provide theoretical explanations on why they may cause the free rider effect. We further develop a query biased node weighting scheme to reduce the free rider effect. In particular, each node is weighted by its proximity to the query node. We define a query biased density metric to integrate the edge and node weights. The query biased densest subgraph, which has the largest query biased density, will shift to the neighborhood of the query nodes after node weighting. We then formulate the query biased densest connected subgraph (QDC) problem, study its complexity, and provide efficient algorithms to solve it. We perform extensive experiments on a variety of real and synthetic networks to evaluate the effectiveness and efficiency of the proposed methods.

MOTIVATION: The emergence of network medicine not only offers more opportunities for better and more complete understanding of the molecular complexities of diseases, but also serves as a promising tool for identifying new drug targets and establishing new relationships among diseases that enable drug repositioning. Computational approaches for drug repositioning by integrating information from multiple sources and multiple levels have the potential to provide great insights to the complex relationships among drugs, targets, disease genes and diseases at a system level. RESULTS: In this article, we have proposed a computational framework based on a heterogeneous network model and applied the approach on drug repositioning by using existing omics data about diseases, drugs and drug targets. The novelty of the framework lies in the fact that the strength between a disease-drug pair is calculated through an iterative algorithm on the heterogeneous graph that also incorporates drug-target information. Comprehensive experimental results show that the proposed approach significantly outperforms several recent approaches. Case studies further illustrate its practical usefulness. AVAILABILITY AND IMPLEMENTATION: http://cbc.case.edu CONTACT: [email protected] SUPPLEMENTARY INFORMATION: Supplementary data are available at Bioinformatics online.

MOTIVATION: For many complex traits/diseases, it is believed that rare variants account for some of the missing heritability that cannot be explained by common variants. Sequencing a large number of samples through DNA pooling is a cost-effective strategy to discover rare variants and to investigate their associations with phenotypes. Overlapping pool designs provide further benefit because such approaches can potentially identify variant carriers, which is important for downstream applications of association analysis of rare variants. However, existing algorithms for analysing sequence data from overlapping pools are limited. RESULTS: We propose a complete data analysis framework for overlapping pool designs, with novelties in all three major steps: variant pool and variant locus identification, variant allele frequency estimation and variant sample decoding. The framework can be used in combination with any design matrix. We have investigated its performance based on two different overlapping designs and have compared it with three state-of-the-art methods, by simulating targeted sequencing and by pooling real sequence data. Results on both datasets show that our algorithm has made significant improvements over existing ones. In conclusion, successful discovery of rare variants and identification of variant carriers using overlapping pool strategies critically depend on many steps, from generation of design matrixes to decoding algorithms. The proposed framework in combination with the design matrixes generated based on the Chinese remainder theorem achieves best overall results. AVAILABILITY: Source code of the program, termed VIP for Variant Identification by Pooling, is available at http://cbc.case.edu/VIP.

BACKGROUND: Somatically-acquired translocations may serve as important markers for assessing the cause and nature of diseases like cancer. Algorithms to locate translocations may use next-generation sequencing (NGS) platform data. However, paired-end strategies do not accurately predict precise translocation breakpoints, and "split-read" methods may lose sensitivity if a translocation boundary is not captured by many sequenced reads. To address these challenges, we have developed "Bellerophon", a method that uses discordant read pairs to identify potential translocations, and subsequently uses "soft-clipped" reads to predict the location of the precise breakpoints. Furthermore, for each chimeric breakpoint, our method attempts to classify it as a participant in an unbalanced translocation, balanced translocation, or interchromosomal insertion. RESULTS: We compared Bellerophon to four previously published algorithms for detecting structural variation (SV). Using two simulated datasets and two prostate cancer datasets, Bellerophon had overall better performance than the other methods. Furthermore, our method accurately predicted the presence of the interchromosomal insertions placed in our simulated dataset, which is an ability that the other SV prediction programs lack. CONCLUSIONS: The combined use of paired reads and soft-clipped reads allows Bellerophon to detect interchromosomal breakpoints with high sensitivity, while also mitigating losses in specificity. This trend is seen across all datasets examined. Because it does not perform assembly on soft-clipped subreads, Bellerophon may be limited in experiments where sequence read lengths are short. AVAILABILITY: The program can be downloaded from http://cbc.case.edu/Bellerophon.

One of the main goals of genome wide association studies (GWAS) has been detecting gene-gene interactions, also known as epistasis in a broad sense, underlying complex diseases. However, high dimensionalities of genotype data and exponential complexity of the search space with respect to the order of targeted interactions make most of existing interaction detection strategies practically inapplicable. Because they are capable of capturing interactions among input variables in addition to the nonlinear effects, decision trees and their ensembles have been recently shown to be resourceful strategies in detecting interactions in GWAS data. However, unlike other nodes, selection of root nodes for decision trees is merely based on marginal effects of candidate variables over the training data, which can greatly limit their epistasis detection performance, especially when disease genotypes have low marginal effects. In this study, we show that modifying the selection criterion of the root node of each new tree joining the ensemble, in a way that captures the interaction with the best variable ranked by the ensemble at the time, leads to a higher power in epistasis detection by decision tree ensembles. We demonstrate the efficacy of this idea using the three most popular decision tree ensemble algorithms: Bagging, Random Forest and Adaboost. Our simulation studies using five two-locus epistasis models with low marginal effects show a considerable enhancement of interaction detection power of all mentioned ensemble strategies after applying the proposed modification.

MOTIVATION: In genome-wide association studies (GWAS), up to millions of single nucleotide polymorphisms (SNPs) are genotyped for thousands of individuals. However, conventional single locus-based approaches are usually unable to detect gene-gene interactions underlying complex diseases. Due to the huge search space for complicated high order interactions, many existing multi-locus approaches are slow and may suffer from low detection power for GWAS. RESULTS: In this article, we develop a simple, fast and effective algorithm to detect genome-wide multi-locus epistatic interactions based on the clustering of relatively frequent items. Extensive experiments on simulated data show that our algorithm is fast and more powerful in general than some recently proposed methods. On a real genome-wide case-control dataset for age-related macular degeneration (AMD), the algorithm has identified genotype combinations that are significantly enriched in the cases. AVAILABILITY: http://www.cs.ucr.edu/~minzhux/EDCF.zip CONTACT: [email protected]; [email protected] SUPPLEMENTARY INFORMATION: Supplementary data are available at Bioinformatics online.

The regulatory mechanism of recombination is a fundamental problem in genomics, with wide applications in genome wide association studies, birth-defect diseases, molecular evolution, cancer research, etc. In mammalian genomes, recombination events cluster into short genomic regions called ¡§recombination hotspots¡¨. Recently, a 13-mer motif enriched in hotspots is identified as a candidate cis-regulatory element of human recombination hotspots, moreover, a zinc finger protein, PRDM9, binds to this motif and is associated with variation of recombination phenotype in human and mouse genomes, thus is a trans-acting regulator of recombination hotspots. However, this pair of cis and trans-regulators covers only a fraction of hotspots, thus other regulators of recombination hotspots remain to be discovered. In this paper, we propose an approach to predicting additional trans-regulators from DNA-binding proteins by comparing their enrichment of binding sites in hotspots. Applying this approach on newly mapped mouse hotspots genome-wide, we confirmed that PRDM9 is a major trans-regulator of hotspots. In addition, a list of top candidate trans-regulators of mouse hotspots is reported. Using GO analysis we observed that the top genes are enriched with function of his tone modification, highlighting the epigenetic regulatory mechanisms of recombination hotspots.

MOTIVATION: Most complex diseases involve multiple genes and their interactions. Although genome-wide association studies (GWAS) have shown some success for identifying genetic variants underlying complex diseases, most existing studies are based on limited single-locus approaches, which detect single nucleotide polymorphisms (SNPs) essentially based on their marginal associations with phenotypes. RESULTS: In this article, we propose an ensemble approach based on boosting to study gene-gene interactions. We extend the basic AdaBoost algorithm by incorporating an intuitive importance score based on Gini impurity to select candidate SNPs. Permutation tests are used to control the statistical significance. We have performed extensive simulation studies using three interaction models to evaluate the efficacy of our approach at realistic GWAS sizes, and have compared it with existing epistatic detection algorithms. Our results indicate that our approach is valid, efficient for GWAS and on disease models with epistasis has more power than existing programs. CONTACT: [email protected].

MicroRNAs are one type of noncoding RNA that regulate their target mRNAs before mRNAs are translated into proteins. Although it has been demonstrated that the regulation is through partial binding of the seed region of a miRNA and its targets, the mechanism of this process is not fully discovered. Some biological experiments have shown that even perfect base pairing in the seed region does not always guarantee the down-regulation of the targets. It has been suspected that some other characteristics of mRNAs may facilitate the regulation. An earlier study (1) has identified five additional features beyond seed matching that seem to significantly affect repressions. However, the observation that evolutionally conserved targets have shown significantly more destabilization comparing to nonconserved targets with the same score using these five features leads to the suspicion that additional features remain to be discovered. This motivates our study to identify additional features that may differentiate down-regulated mRNAs (positive set) from those not down-regulated ones (negative set) provided both sets have perfect seed matches with miRNAs. Our first attempt to search for different sequence motifs around seed site regions in the two different sets is not successful. We further construct a set of 18 sequence/structure features based on domain knowledge and evaluate them individually and jointly. By employing feature selection techniques in combination with several classification methods, we have been able to identify a subset of features that may facilitate the down-regulation of mRNAs. Our results can be incorporated into target prediction algorithms to further improve target specificities.

MOTIVATION: Inference of identical-by-descent (IBD) probabilities is the key in family-based linkage analysis. Using high-density single nucleotide polymorphism (SNP) markers, one can almost always infer haplotype configurations of each member in a family given all individuals being typed. Consequently, the IBD status can be obtained directly from haplotype configurations. However, in reality, many family members are not typed due to practical reasons. The problem of IBD/haplotype inference is much harder when treating untyped individuals as missing. RESULTS: We present a novel hidden Markov model (HMM) approach to infer the IBD status in a pedigree with many untyped members using high-density SNP markers. We introduce the concept of inheritance-generating function, defined for any pair of alleles in a descent graph based on a pedigree structure. We derive a recursive formula for efficient calculation of the inheritance-generating function. By aggregating all possible inheritance patterns via an explicit representation of the number and lengths of all possible paths between two alleles, the inheritance-generating function provides a convenient way to theoretically derive the transition probabilities of the HMM. We further extend the basic HMM to incorporate population linkage disequilibrium (LD). Pedigree-wise IBD sharing can be constructed based on pair-wise IBD relationships. Compared with traditional approaches for linkage analysis, our new model can efficiently infer IBD status without enumerating all possible genotypes and transmission patterns of untyped members in a family. Our approach can be reliably applied on large pedigrees with many untyped members, and the inferred IBD status can be used for non-parametric genome-wide linkage analysis. AVAILABILITY: The algorithm is implemented in Matlab and is freely available upon request. SUPPLEMENTARY INFORMATION: Supplementary data are available on Bioinformatics online.

UNLABELLED: We describe the features and implementation of a web application tool named MAVEN--for Management, Analysis, Visualization and rEsults shariNg of genome-wide association data using cutting edge technologies. Main capabilities include user data uploading and management, queries using a variety of criteria, visualization of results, interactive selections and seamless integration of users' data with databases at the National Center for Biotechnology Information (NCBI) for functional annotations of single nucleotide polymorphisms (SNPs) and genes. AVAILABILITY: http://cbc.case.edu/maven. SUPPLEMENTARY INFORMATION: Supplementary data are available at Bioinformatics online.

BACKGROUND: Haplotype-based approaches have been extensively studied for case-control association mapping in recent years. It has been shown that haplotype methods can provide more consistent results comparing to single-locus based approaches, especially in cases where causal variants are not typed. Improved power has been observed by clustering similar or rare haplotypes into groups to reduce the degrees of freedom of association tests. For family-based association studies, one commonly used strategy is Transmission Disequilibrium Tests (TDT), which examine the imbalanced transmission of alleles/haplotypes to affected and normal children. Many extensions have been developed to deal with general pedigrees and continuous traits. RESULTS: In this paper, we propose a new haplotype-based association method for family data that is different from the TDT framework. Our approach (termed F_HapMiner) is based on our previous successful experiences on haplotype inference from pedigree data and haplotype-based association mapping. It first infers diplotype pairs of each individual in each pedigree assuming no recombination within a family. A phenotype score is then defined for each founder haplotype. Finally, F_HapMiner applies a clustering algorithm on those founder haplotypes based on their similarities and identifies haplotype clusters that show significant associations with diseases/traits. We have performed extensive simulations based on realistic assumptions to evaluate the effectiveness of the proposed approach by considering different factors such as allele frequency, linkage disequilibrium (LD) structure, disease model and sample size. Comparisons with single-locus and haplotype-based TDT methods demonstrate that our approach consistently outperforms the TDT-based approaches regardless of disease models, local LD structures or allele/haplotype frequencies. CONCLUSION: We present a novel haplotype-based association approach using family data. Experiment results demonstrate that it achieves significantly higher power than TDT-based approaches.

BACKGROUND: The human leukocyte antigen system (HLA) contains many highly variable genes. HLA genes play an important role in the human immune system, and HLA gene matching is crucial for the success of human organ transplantations. Numerous studies have demonstrated that variation in HLA genes is associated with many autoimmune, inflammatory and infectious diseases. However, typing HLA genes by serology or PCR is time consuming and expensive, which limits large-scale studies involving HLA genes. Since it is much easier and cheaper to obtain single nucleotide polymorphism (SNP) genotype data, accurate computational algorithms to infer HLA gene types from SNP genotype data are in need. To infer HLA types from SNP genotypes, the first step is to infer SNP haplotypes from genotypes. However, for the same SNP genotype data set, the haplotype configurations inferred by different methods are usually inconsistent, and it is often difficult to decide which one is true. RESULTS: In this paper, we design an accurate HLA gene type inference algorithm by utilizing SNP genotype data from pedigrees, known HLA gene types of some individuals and the relationship between inferred SNP haplotypes and HLA gene types. Given a set of haplotypes inferred from the genotypes of a population consisting of many pedigrees, the algorithm first constructs a weighted similarity graph based on a new haplotype similarity measure and derives constraint edges from known HLA gene types. Based on the principle that different HLA gene alleles should have different background haplotypes, the algorithm searches for an optimal labeling of all the haplotypes with unknown HLA gene types such that the total weight among the same HLA gene types is maximized. To deal with ambiguous haplotype solutions, we use a genetic algorithm to select haplotype configurations that tend to maximize the same optimization criterion. Our experiments on a previously typed subset of the HapMap data show that the algorithm is highly accurate, achieving an accuracy of 96% for gene HLA-A, 95% for HLA-B, 97% for HLA-C, 84% for HLA-DRB1, 98% for HLA-DQA1 and 97% for HLA-DQB1 in a leave-one-out test. CONCLUSIONS: Our algorithm can infer HLA gene types from neighboring SNP genotype data accurately. Compared with a recent approach on the same input data, our algorithm achieved a higher accuracy. The code of our algorithm is available to the public for free upon request to the corresponding authors.

A comprehensive understanding of cancer progression may shed light on genetic and molecular mechanisms of oncogenesis, and it may provide much needed information for effective diagnosis, prognosis, and optimal therapy. However, despite considerable effort in studying cancer progressions, their molecular and genetic basis remains largely unknown. Microarray experiments can systematically assay gene expressions across genome, therefore they have been widely used to gain insights on cancer progressions. In general, expression data may be obtained from different stages of the same samples. More often, data were obtained from individuals at different stages. Existing methods such as the Student's t-test and clustering approaches focus on identification of differentially expressed genes in different stages, but they are not suitable for capturing real progression signatures across all progression stages. We propose an alternative approach, namely a multicategory logit model, to identify novel genes that show significant correlations across multiple stages. We have applied the approach on a real data set concerning prostate cancer progression and obtained a set of genes that show consistency trends across multiple stages. Further analysis based on Gene Ontology (GO) annotations, protein-protein interaction networks and KEGG pathways databases, as well as literature search demonstrates that our candidate list not only includes some well-known prostate cancer related genes such as MYC and AMACR, but also consists of novel genes (e.g. CKS2) that have been confirmed by very recent independent studies. Our results illustrate that ordinal analysis of cancer progression data has the potential to obtain a set of promising candidate genes. Such a list can be further prioritized by combining other existing biomedical knowledge to identify therapeutic targets and/or biomarkers of cancer progressions.

BACKGROUND: In systems biology, comparative analyses of molecular interactions across diverse species indicate that conservation and divergence of networks can be used to understand functional evolution from a systems perspective. A key characteristic of these networks is their modularity, which contributes significantly to their robustness, as well as adaptability. Consequently, analysis of modular network structures from a phylogenetic perspective may be useful in understanding the emergence, conservation, and diversification of functional modularity. RESULTS: In this paper, we propose a phylogenetic framework for analyzing network modules, with applications that extend well beyond network-based phylogeny reconstruction. Our approach is based on identification of modular network components from each network separately, followed by projection of these modules onto the networks of other species to compare different networks. Subsequently, we use the conservation of various modules in each network to assess the similarity between different networks. Compared to traditional methods that rely on topological comparisons, our approach has key advantages in (i) avoiding intractable graph comparison problems in comparative network analysis, (ii) accounting for noise and missing data through flexible treatment of network conservation, and (iii) providing insights on the evolution of biological systems through investigation of the evolutionary trajectories of network modules. We test our method, MOPHY, on synthetic data generated by simulation of network evolution, as well as existing protein-protein interaction data for seven diverse species. Comprehensive experimental results show that MOPHY is promising in reconstructing evolutionary histories of extant networks based on conservation of modularity, it is highly robust to noise, and outperforms existing methods that quantify network similarity in terms of conservation of network topology. CONCLUSION: These results establish modularity and network proximity as useful features in comparative network analysis and motivate detailed studies of the evolutionary histories of network modules.

BACKGROUND: With the completion of the HapMap project, a variety of computational algorithms and tools have been proposed for haplotype inference, tag SNP selection and genome-wide association studies. Simulated data are commonly used in evaluating these new developed approaches. In addition to simulations based on population models, empirical data generated by perturbing real data, has also been used because it may inherit specific properties from real data. However, there is no tool that is publicly available to generate large scale simulated variation data by taking into account knowledge from the HapMap project. RESULTS: A computer program (gs) was developed to quickly generate a large number of samples based on real data that are useful for a variety of purposes, including evaluating methods for haplotype inference, tag SNP selection and association studies. Two approaches have been implemented to generate dense SNP haplotype/genotype data that share similar local linkage disequilibrium (LD) patterns as those in human populations. The first approach takes haplotype pairs from samples as inputs, and the second approach takes patterns of haplotype block structures as inputs. Both quantitative and qualitative traits have been incorporated in the program. Phenotypes are generated based on a disease model, or based on the effect of a quantitative trait nucleotide, both of which can be specified by users. In addition to single-locus disease models, two-locus disease models have also been implemented that can incorporate any degree of epistasis. Users are allowed to specify all nine parameters in a 3 x 3 penetrance table. For several commonly used two-locus disease models, the program can automatically calculate penetrances based on the population prevalence and marginal effects of a disease that users can conveniently specify. CONCLUSION: The program gs can effectively generate large scale genetic and phenotypic variation data that can be used for evaluating new developed approaches. It is freely available from the authors' web site at http://www.eecs.case.edu/~jxl175/gs.html.

BACKGROUND: With the availability of large-scale, high-density single-nucleotide polymorphism (SNP) markers, substantial effort has been made in identifying disease-causing genes using linkage disequilibrium (LD) mapping by haplotype analysis of unrelated individuals. In addition to complex diseases, many continuously distributed quantitative traits are of primary clinical and health significance. However the development of association mapping methods using unrelated individuals for quantitative traits has received relatively less attention. RESULTS: We recently developed an association mapping method for complex diseases by mining the sharing of haplotype segments (i.e., phased genotype pairs) in affected individuals that are rarely present in normal individuals. In this paper, we extend our previous work to address the problem of quantitative trait mapping from unrelated individuals. The method is non-parametric in nature, and statistical significance can be obtained by a permutation test. It can also be incorporated into the one-way ANCOVA (analysis of covariance) framework so that other factors and covariates can be easily incorporated. The effectiveness of the approach is demonstrated by extensive experimental studies using both simulated and real data sets. The results show that our haplotype-based approach is more robust than two statistical methods based on single markers: a single SNP association test (SSA) and the Mann-Whitney U-test (MWU). The algorithm has been incorporated into our existing software package called HapMiner, which is available from our website at http://www.eecs.case.edu/~jxl175/HapMiner.html. CONCLUSION: For QTL (quantitative trait loci) fine mapping, to identify QTNs (quantitative trait nucleotides) with realistic effects (the contribution of each QTN less than 10% of total variance of the trait), large samples sizes (>or= 500) are needed for all the methods. The overall performance of HapMiner is better than that of the other two methods. Its effectiveness further depends on other factors such as recombination rates and the density of typed SNPs. Haplotype-based methods might provide higher power than methods based on a single SNP when using tag SNPs selected from a small number of samples or some other sources (such as HapMap data). Rank-based statistics usually have much lower power, as shown in our study.

MOTIVATION: With the availability of large-scale, high-density single-nucleotide polymorphism markers and information on haplotype structures and frequencies, a great challenge is how to take advantage of haplotype information in the association mapping of complex diseases in case-control studies. RESULTS: We present a novel approach for association mapping based on directly mining haplotypes (i.e. phased genotype pairs) produced from case-control data or case-parent data via a density-based clustering algorithm, which can be applied to whole-genome screens as well as candidate-gene studies in small genomic regions. The method directly explores the sharing of haplotype segments in affected individuals that are rarely present in normal individuals. The measure of sharing between two haplotypes is defined by a new similarity metric that combines the length of the shared segments and the number of common alleles around any marker position of the haplotypes, which is robust against recent mutations/genotype errors and recombination events. The effectiveness of the approach is demonstrated by using both simulated datasets and real datasets. The results show that the algorithm is accurate for different population models and for different disease models, even for genes with small effects, and it outperforms some recently developed methods.

We study the problem of reconstructing haplotype configurations from genotypes on pedigree data with missing alleles under the Mendelian law of inheritance and the minimum recombination principle, which is important for the construction of haplotype maps and genetic linkage/association analysis. Our previous results show that the problem of finding a minimum-recombinant haplotype configuration (MRHC) is in general NP-hard. The existing algorithms for MRHC either are heuristic in nature and cannot guarantee optimality, or only work under some restrictions (on e.g. the size and structure of the input pedigree, the number of marker loci, the number of recombinants in the pedigree, etc.). In addition, most of them cannot handle data with missing alleles and, for those that do consider missing data, they usually do not perform well in terms of minimizing the number of recombinants when a significant fraction of alleles are missing. In this paper, we develop an effective integer linear programming (ILP) formulation of the MRHC problem with missing data and a branch-and-bound strategy that utilizes a partial order relationship (and some other special relationships) among variables to decide the branching order. The partial order relationship is discovered in the preprocessing of constraints by considering unique properties in our ILP formulation. A directed graph is built based on the variables and their partial order relationship. By identifying and collapsing the strongly connected components in the graph, we may greatly reduce the size of an ILP instance. Non-trivial (lower and upper) bounds on the optimal number of recombinants are introduced at each branching node to effectively prune the search tree. When multiple solutions exist, a best haplotype configuration is selected based on a maximum likelihood approach. Our results on simulated data show that the algorithm could recover haplotypes with 50 loci from a pedigree of size 29 in seconds on a standard PC. Its accuracy is more than 99.8% for data with no missing alleles and 98.3% for data with 20% missing alleles in terms of correctly recovered phase information at each marker locus. As an application of our algorithm to real data, we present some test results on reconstructing haplotypes from a genome-scale SNP data set consisting of 12 pedigrees that have 0.8% to 14.5% missing alleles.

We study haplotype reconstruction under the Mendelian law of inheritance and the minimum recombination principleon pedigree data. We prove that the problem of finding a mini-mum-recombinant haplotype configuration (MRHC) is in general NP-hard. This is the first complexity result concerning the problem to our knowledge. An iterative algorithm based on blocks of consecutive resolved marker loci (called block-extension) is proposed. It is very efficient and can be used for large pedigrees with a large number of markers, especially for those data sets requiring few recombinants (or recombination events). A polynomial-time exact algorithm for haplotype reconstruction without recombinants is also presented. This algorithm first identifies all the necessary constraints based on the Mendelian law and the zero recombinant assumption, and represents them using a system of linear equations over the cyclic group Z2. By using a simple method based on Gaussian elimination, we could obtain all possible feasible haplotype configurations. We have tested the block-extension algorithm on simulated data generated on three pedigree structures. The results show that the algorithm performs very well on both multi-allelic and biallelic data, especially when the number of recombinants is small.