Accurate prediction of drug sensitivity not only enhances the efficacy of personalized therapies but also provides valuable insights into the mechanisms underlying drug resistance. Despite significant progress, current computational approaches remain limited by their insufficient integration of prior biological knowledge and suboptimal representation of cell lines and drugs. We propose GPK-DSP, a graph-based approach to mitigate these limitations by: (1) Constructing comprehensive representations of cell lines through the integration of interaction and co-expression networks derived from cancer-associated critical genes; (2) Generating comprehensive drug embeddings using a hybrid architecture combining graph convolutional networks (for SMILES sequences) and multi-layer perceptrons (for molecular fingerprints); (3) Optimizing feature learning via graph learning on an adaptive Gaussian similarity-based heterogeneous graph. When evaluated on the CCLE and GDSC benchmark datasets, GPKDSP demonstrated superior predictive performance, achieving AUC scores of 0.8954 and 0.8782, respectively, and substantially outperforming existing state-of-the-art methods.

Predicting cancer patient responses to anticancer drugs is essential for precision therapy and remains a central challenge in oncology research. Existing drug response prediction (DRP) methods often suffer from noisy, redundant multi-omics data, suboptimal cross-omics integration, and incomplete fusion of multimodal drug representations. In this study, we propose MIXA-DRP, a unified deep learning framework that leverages a bidirectional multi-head cross-attention mechanism to jointly integrate cancer cell omics (gene expression, mutation, and DNA methylation) and diverse drug features (molecular graphs, SMILES, and Morgan fingerprints). Final response predictions are produced via stacked fully connected layers. Benchmarking demonstrates that MIXA-DRP achieved the best overall performance in all metrics, with an RMSE of 1.0156, R2 of 0.8573, PCC of 0.9277, and SCC of 0.9049, outperforming every baseline. Ablation studies confirm the effectiveness of each modality and the cross-attention architecture. Case studies further validate its practical utility in predicting responses for novel anticancer agents. MIXA-DRP offers a robust, interpretable solution for DRP, advancing precision medicine by delivering accurate, clin-ically actionable predictions.

Enhancer-Promoter Interactions (EPIs) play a crucial role in gene expression regulation. However, traditional experimental methods for detecting EPIs are often time-consuming and costly, prompting a growing demand for computational approaches. In this work, we propose a novel deep-learning model, termed EPI-RMDL, for the prediction of enhancer-promoter interactions based only on the DNA sequences. EPI-RMDL at first encodes the DNA sequences of a set of enhancers and promoters into an information matrix via the dna2vec method. Subsequently, local and global features are extracted from the matrix using a three-layer convolution neural network. Then, the features are processed through three RoFormers, which are enhanced transformers with Rotary Position Embedding (RoPE), in order to obtain relative positional information and interaction details between promoters and enhancers. Finally, a special matching mechanism is incorporated to analyze the interplay among the output vectors generated by the front-end RoFormers. We trained a general model by integrating data from six distinct cell lines and fine-tuned it with specific cell-line data to obtain an optimal model EPI-RMDL best for each cell line. Benchmarking against six state-of-the-art methods using datasets from six cell lines, our model demonstrates superior performance. Specifically, the EPI-RMDL_best model achieves a mean AUROC of 95.8% and an average AUPR of 80.8%.

Medical image segmentation and classification are both crucial components of computer-aided diagnosis, and past studies have identified the inherent correlations between them in various cases. Numerous multi-task models have been developed, with most leveraging shared features extracted by a feature extractor to address both tasks. However, few have paid attention to the feature differences between them which may be obvious when the segmentation object area is larger than the classification object area. To address the issue, we introduce a model named SCMTL-LSFG, which employs a low-level feature sharing and high-level inter-feature guidance strategy. SCMTL-LSFG comprises a segmentation branch and a classification branch, which share a low-level feature extraction component but have two separate high-level feature extraction components. Since there are correlations between the two tasks, SCMTL-LSFG leverages the segmentation component to guide the classification component in high-level feature extraction by the Inter-Feature Guidance module we design. The evaluation conducted on a public breast ultrasound image dataset and a COVID-19 chest X-ray image dataset indicates that SCMTL-LSFG effectively improves classification accuracy. Our experiment results also demonstrated that SCMTL-LSFG significantly outperforms three state-of-art similar models in both tasks.

Medication recommendation is a crucial application of artificial intelligence in healthcare. Current methodologies mostly depend on patient-level longitudinal representation, which utilizes the entirety of historical electronic health records for making predictions. However, they tend to overlook a few key elements: (1) The need to analyze the impact of past medications on previous conditions. (2) Similarity in patient visits is more common than similarity in the complete medical histories of patients. (3) It is difficult to accurately represent patient-level longitudinal data due to the varying numbers of visits. To our knowledge, current models face difficulties in dealing with initial patient visits (i.e. in cold-start scenarios) which are common in clinical practice. This paper introduces DrugDoctor, an innovative drug recommendation model crafted to emulate the decision-making mechanics of human doctors. Unlike previous methods, DrugDoctor explores the visit-level relationship between prescriptions and diseases while considering the impact of past prescriptions on the patient's condition to provide more accurate recommendations. We design a plug-and-play block to effectively capture drug substructure-aware disease information and effectiveness-aware medication information, employing cross-attention and multi-head self-attention mechanisms. Furthermore, DrugDoctor adopts a fundamentally new visit-level training strategy, aligning more closely with the practices of doctors. Extensive experiments conducted on the MIMIC-III and MIMIC-IV datasets demonstrate that DrugDoctor outperforms 10 other state-of-the-art methods in terms of Jaccard, F1-score, and PRAUC. Moreover, DrugDoctor exhibits strong robustness in handling patients with varying numbers of visits and effectively tackles "cold-start" issues in medication combination recommendations.

MOTIVATION: The identification of cancer subtypes plays a crucial role in cancer research and treatment. With the rapid development of high-throughput sequencing technologies, there has been an exponential accumulation of cancer multi-omics data. Integrating multi-omics data has emerged as a cost-effective and efficient strategy for cancer subtyping. While current methods primarily rely on genomics data, protein expression data offers a closer representation of phenotype. Therefore, integrating protein expression data holds promise for enhancing subtyping accuracy. However, the scarcity of protein expression data compared to genomics data presents a challenge in its direct incorporation into existing methods. Moreover, striking a balance between omics-specific learning and cross-omics learning remains a prevalent challenge in current multi-omics integration methods. RESULTS: We introduce Subtype-MGTP, a novel cancer subtyping framework based on the translation of Multiple Genomics To Proteomics. Subtype-MGTP comprises two modules: a translation module, which leverages available protein data to translate multi-type genomics data into predicted protein expression data, and an improved deep subspace clustering module, which integrates contrastive learning to cluster the predicted protein data, yielding refined subtyping results. Extensive experiments conducted on benchmark datasets demonstrate that Subtype-MGTP outperforms nine state-of-the-art cancer subtyping methods. The interpretability of clustering results is further supported by the clinical and survival analysis. Subtype-MGTP also exhibits strong robustness against varying rates of missing protein data and demonstrates distinct advantages in integrating multi-omics data with imbalanced multi-omics data. AVAILABILITY AND IMPLEMENTATION: The code and results are available at https://github.com/kybinn/Subtype-MGTP.

Identifying cancer subtypes is an essential component of precision medicine, as it helps researchers develop more precise treatment methods and prevention strategies. Meanwhile, high-throughput sequencing technologies have produced a huge amount of multi-omics data for cancer patients and make it is practical to subtype cancers using multi-omics data. As existing cancer subtyping computational models based on multi-omics data could not effectively extended to weakly paired omics data, we proposed a novel unsupervised cancer subtyping model Subtype-DCGCN. Subtype-DCGCN uses Dual Contrast Graph Convolutional Networks guided by dual contrastive learning to lean low dimensional features for each type omics data, and with weighted average fusion Subtype-DCGCN could deal well with weakly paired multi-omics data. Extensive experiments on benchmark datasets showed that Subtype-DCGCN exhibited superior performance to other eight state-of-the-art similar methods in general to identify cancer subtypes. Moreover, tests on simulated datasets with varying missing rate showed that Subtype-DCGCN performed pretty well on weakly paired omics datasets.

Abstract Background Identifying drug–target interactions (DTIs) plays a key role in drug development. Traditional wet experiments to identify DTIs are costly and time consuming. Effective computational methods to predict DTIs are useful to speed up the process of drug discovery. A variety of non-negativity matrix factorization based methods are proposed to predict DTIs, but most of them overlooked the sparsity of feature matrices and the convergence of adopted matrix factorization algorithms, therefore their performances can be further improved. Results In order to predict DTIs more accurately, we propose a novel method iPALM-DLMF. iPALM-DLMF models DTIs prediction as a problem of non-negative matrix factorization with graph dual regularization terms and $$L_{2,1}$$ L 2 , 1 norm regularization terms. The graph dual regularization terms are used to integrate the information from the drug similarity matrix and the target similarity matrix, and $$L_{2,1}$$ L 2 , 1 norm regularization terms are used to ensure the sparsity of the feature matrices obtained by non-negative matrix factorization. To solve the model, iPALM-DLMF adopts non-negative double singular value decomposition to initialize the nonnegative matrix factorization, and an inertial Proximal Alternating Linearized Minimization iterating process, which has been proved to converge to a KKT point, to obtain the final result of the matrix factorization. Extensive experimental results show that iPALM-DLMF has better performance than other state-of-the-art methods. In case studies, in 50 highest-scoring proteins targeted by the drug gabapentin predicted by iPALM-DLMF, 46 have been validated, and in 50 highest-scoring drugs targeting prostaglandin-endoperoxide synthase 2 predicted by iPALM-DLMF, 47 have been validated.

BACKGROUND: Knowing the responses of a patient to drugs is essential to make personalized medicine practical. Since the current clinical drug response experiments are time-consuming and expensive, utilizing human genomic information and drug molecular characteristics to predict drug responses is of urgent importance. Although a variety of computational drug response prediction methods have been proposed, their effectiveness is still not satisfying. RESULTS: In this study, we propose a method called LGRDRP (Learning Graph Representation for Drug Response Prediction) to predict cell line-drug responses. At first, LGRDRP constructs a heterogeneous network integrating multiple kinds of information: cell line miRNA expression profiles, drug chemical structure similarity, gene-gene interaction, cell line-gene interaction and known cell line-drug responses. Then, for each cell line, learning graph representation and Laplacian feature selection are combined to obtain network topology features related to the cell line. The learning graph representation method learns network topology structure features, and the Laplacian feature selection method further selects out some most important ones from them. Finally, LGRDRP trains an SVM model to predict drug responses based on the selected features of the known cell line-drug responses. Our five-fold cross-validation results show that LGRDRP is significantly superior to the art-of-the-state methods in the measures of the average area under the receiver operating characteristics curve, the average area under the precision-recall curve and the recall rate of top-k predicted sensitive cell lines. CONCLUSIONS: Our results demonstrated that the usage of multiple types of information about cell lines and drugs, the learning graph representation method, and the Laplacian feature selection is useful to the improvement of performance in predicting drug responses. We believe that such an approach would be easily extended to similar problems such as miRNA-disease relationship inference.

BACKGROUND: Identifying drug-target interactions (DTIs) plays a key role in drug development. Traditional wet experiments to identify DTIs are expensive and time consuming. Effective computational methods to predict DTIs are useful to narrow the searching scope of potential drugs and speed up the process of drug discovery. There are a variety of non-negativity matrix factorization based methods to predict DTIs, but the convergence of the algorithms used in the matrix factorization are often overlooked and the results can be further improved. RESULTS: In order to predict DTIs more accurately and quickly, we propose an alternating direction algorithm to solve graph regularized non-negative matrix factorization with prior knowledge consistency constraint (ADA-GRMFC). Based on known DTIs, drug chemical structures and target sequences, ADA-GRMFC at first constructs a DTI matrix, a drug similarity matrix and a target similarity matrix. Then DTI prediction is modeled as the non-negative factorization of the DTI matrix with graph dual regularization terms and a prior knowledge consistency constraint. The graph dual regularization terms are used to integrate the information from the drug similarity matrix and the target similarity matrix, and the prior knowledge consistency constraint is used to ensure the matrix decomposition result should be consistent with the prior knowledge of known DTIs. Finally, an alternating direction algorithm is used to solve the matrix factorization. Furthermore, we prove that the algorithm can converge to a stationary point. Extensive experimental results of 10-fold cross-validation show that ADA-GRMFC has better performance than other state-of-the-art methods. In the case study, ADA-GRMFC is also used to predict the targets interacting with the drug olanzapine, and all of the 10 highest-scoring targets have been accurately predicted. In predicting drug interactions with target estrogen receptors alpha, 17 of the 20 highest-scoring drugs have been validated.

Proteins are dominant executors of living processes. Compared to genetic variations, changes in the molecular structure and state of a protein (i.e. proteoforms) are more directly related to pathological changes in diseases. Characterizing proteoforms involves identifying and locating primary structure alterations (PSAs) in proteoforms, which is of practical importance for the advancement of the medical profession. With the development of mass spectrometry (MS) technology, the characterization of proteoforms based on top-down MS technology has become possible. This type of method is relatively new and faces many challenges. Since the proteoform identification is the most important process in characterizing proteoforms, we comprehensively review the existing proteoform identification methods in this study. Before identifying proteoforms, the spectra need to be preprocessed, and protein sequence databases can be filtered to speed up the identification. Therefore, we also summarize some popular deconvolution algorithms, various filtering algorithms for improving the proteoform identification performance and various scoring methods for localizing proteoforms. Moreover, commonly used methods were evaluated and compared in this review. We believe our review could help researchers better understand the current state of the development in this field and design new efficient algorithms for the proteoform characterization.

BACKGROUND: Long non-coding RNAs (lncRNAs) regulate diverse biological processes via interactions with proteins. Since the experimental methods to identify these interactions are expensive and time-consuming, many computational methods have been proposed. Although these computational methods have achieved promising prediction performance, they neglect the fact that a gene may encode multiple protein isoforms and different isoforms of the same gene may interact differently with the same lncRNA. RESULTS: In this study, we propose a novel method, DeepLPI, for predicting the interactions between lncRNAs and protein isoforms. Our method uses sequence and structure data to extract intrinsic features and expression data to extract topological features. To combine these different data, we adopt a hybrid framework by integrating a multimodal deep learning neural network and a conditional random field. To overcome the lack of known interactions between lncRNAs and protein isoforms, we apply a multiple instance learning (MIL) approach. In our experiment concerning the human lncRNA-protein interactions in the NPInter v3.0 database, DeepLPI improved the prediction performance by 4.7% in term of AUC and 5.9% in term of AUPRC over the state-of-the-art methods. Our further correlation analyses between interactive lncRNAs and protein isoforms also illustrated that their co-expression information helped predict the interactions. Finally, we give some examples where DeepLPI was able to outperform the other methods in predicting mouse lncRNA-protein interactions and novel human lncRNA-protein interactions. CONCLUSION: Our results demonstrated that the use of isoforms and MIL contributed significantly to the improvement of performance in predicting lncRNA and protein interactions. We believe that such an approach would find more applications in predicting other functional roles of RNAs and proteins.

BACKGROUND: Some proposed methods for identifying essential proteins have better results by using biological information. Gene expression data is generally used to identify essential proteins. However, gene expression data is prone to fluctuations, which may affect the accuracy of essential protein identification. Therefore, we propose an essential protein identification method based on gene expression and the PPI network data to calculate the similarity of "active" and "inactive" state of gene expression in a cluster of the PPI network. Our experiments show that the method can improve the accuracy in predicting essential proteins. RESULTS: In this paper, we propose a new measure named JDC, which is based on the PPI network data and gene expression data. The JDC method offers a dynamic threshold method to binarize gene expression data. After that, it combines the degree centrality and Jaccard similarity index to calculate the JDC score for each protein in the PPI network. We benchmark the JDC method on four organisms respectively, and evaluate our method by using ROC analysis, modular analysis, jackknife analysis, overlapping analysis, top analysis, and accuracy analysis. The results show that the performance of JDC is better than DC, IC, EC, SC, BC, CC, NC, PeC, and WDC. We compare JDC with both NF-PIN and TS-PIN methods, which predict essential proteins through active PPI networks constructed from dynamic gene expression. CONCLUSIONS: We demonstrate that the new centrality measure, JDC, is more efficient than state-of-the-art prediction methods with same input. The main ideas behind JDC are as follows: (1) Essential proteins are generally densely connected clusters in the PPI network. (2) Binarizing gene expression data can screen out fluctuations in gene expression profiles. (3) The essentiality of the protein depends on the similarity of "active" and "inactive" state of gene expression in a cluster of the PPI network.

MOTIVATION: Advances in high-throughput genotyping and sequencing technologies during recent years have revealed essential roles of non-coding regions in gene regulation. Genome-wide association studies (GWAS) suggested that a large proportion of risk variants are located in non-coding regions and remain unexplained by current expression quantitative trait loci catalogs. Interpreting the causal effects of these genetic modifications is crucial but difficult owing to our limited knowledge of how regulatory elements function. Although several computational methods have been designed to prioritize regulatory variants that substantially impact human phenotypes, few of them achieve consistently high performance even when large-scale multi-omic data are integrated. RESULTS: We propose a novel multi-task framework based on Bayesian deep neural networks, MtBNN, to quantify the deleterious impact of single nucleotide polymorphisms in non-coding genomic regions. With the high-efficiency provided by the multi-task Bayesian framework to integrate information from different sources, MtBNN is capable of extracting features from genomic sequences of large-scale chromatin-profiling data, such as chromatin accessibility and transcript factor binding affinities, and calculating the distribution of the probability that a non-coding variant disrupts regulatory activities. A series of comprehensive experiments show that MtBNN quantifies the functional impact of cis-regulatory variations with high accuracy, including expression quantitative trait locus, DNase I sensitivity quantitative trait locus and functional genetic variants located within ATAC-peaks that affect the accessibility of the corresponding peak and achieves significantly better performance than the existing methods. Moreover, MtBNN has applications in the discovery of potentially causal disease-associated single-nucleotide polymorphisms (SNPs), thus helping fine-map the GWAS SNPs. AVAILABILITY AND IMPLEMENTATION: Code can be downloaded from https://github.com/Zoesgithub/MtBNN. SUPPLEMENTARY INFORMATION: Supplementary data are available at Bioinformatics online.

MOTIVATION: Some economically important plants including wheat and cotton have more than two copies of each chromosome. With the decreasing cost and increasing read length of next-generation sequencing technologies, reconstructing the multiple haplotypes of a polyploid genome from its sequence reads becomes practical. However, the computational challenge in polyploid haplotyping is much greater than that in diploid haplotyping, and there are few related methods. RESULTS: This article models the polyploid haplotyping problem as an optimal poly-partition problem of the reads, called the Polyploid Balanced Optimal Partition model. For the reads sequenced from a k-ploid genome, the model tries to divide the reads into k groups such that the difference between the reads of the same group is minimized while the difference between the reads of different groups is maximized. When the genotype information is available, the model is extended to the Polyploid Balanced Optimal Partition with Genotype constraint problem. These models are all NP-hard. We propose two heuristic algorithms, H-PoP and H-PoPG, based on dynamic programming and a strategy of limiting the number of intermediate solutions at each iteration, to solve the two models, respectively. Extensive experimental results on simulated and real data show that our algorithms can solve the models effectively, and are much faster and more accurate than the recent state-of-the-art polyploid haplotyping algorithms. The experiments also show that our algorithms can deal with long reads and deep read coverage effectively and accurately. Furthermore, H-PoP might be applied to help determine the ploidy of an organism. AVAILABILITY AND IMPLEMENTATION: https://github.com/MinzhuXie/H-PoPG CONTACT: [email protected] information: Supplementary data are available at Bioinformatics online.

Single nucleotide polymorphisms, a dominant type of genetic variants, have been used successfully to identify defective genes causing human single gene diseases. However, most common human diseases are complex diseases and caused by gene-gene and gene-environment interactions. Many SNP-SNP interaction analysis methods have been introduced but they are not powerful enough to discover interactions more than three SNPs. The paper proposes a novel method that analyzes all SNPs simultaneously. Different from existing methods, the method regards an individual's genotype data on a list of SNPs as a point with a unit of energy in a multi-dimensional space, and tries to find a new coordinate system where the energy distribution difference between cases and controls reaches the maximum. The method will find different multiple SNPs combinatorial patterns between cases and controls based on the new coordinate system. The experiment on simulated data shows that the method is efficient. The tests on the real data of age-related macular degeneration (AMD) disease show that it can find out more significant multi-SNP combinatorial patterns than existing methods.

Phased haplotype information is crucial in our complete understanding of differences between individuals at the genetic level. Given a collection of DNA fragments sequenced from a homologous pair of chromosomes, the problem of single individual haplotyping (SIH) aims to reconstruct a pair of haplotypes using a computer algorithm. In this paper, we encode the information of aligned DNA fragments into a two-locus linkage graph and approach the SIH problem by vertex labeling of the graph. In order to find a vertex labeling with the minimum sum of weights of incompatible edges, we develop a fast and accurate heuristic algorithm. It starts with detecting error-tolerant components by an adapted breadth-first search. A proper labeling of vertices is then identified for each component, with which sequencing errors are further corrected and edge weights are adjusted accordingly. After contracting each error-tolerant component into a single vertex, the above procedure is iterated on the resulting condensed linkage graph until error-tolerant components are no longer detected. The algorithm finally outputs a haplotype pair based on the vertex labeling. Extensive experiments on simulated and real data show that our algorithm is more accurate and faster than five existing algorithms for single individual haplotyping.

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.

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.

Haplotypes are more useful in complex disease gene mapping than single-nucleotide polymorphisms (SNPs). However, haplotypes are difficult to obtain directly using biological experiments, which has prompted research into efficient computational methods for determining haplotypes. The individual haplotyping problem called Minimum Letter Flip (MLF) is a computational problem that, given a set of aligned DNA sequence fragment data of an individual, induces the corresponding haplotypes by flipping minimum SNPs. There has been no practical exact algorithm for solving the problem. Due to technical limits in DNA sequencing experiments, the maximum length of a fragment sequenced directly is about 1kb. In consequence, with a genome-average SNP density of 1.84 SNPs per 1 kb of DNA sequence, the maximum number k1 of SNP sites that a fragment covers is usually small. Moreover, in order to save time and money, the maximum number k2 of fragments that cover an SNP site is usually no more than 19. Building on these fragment data properties, the current paper introduces a new parameterised algorithm with running time O(nk22k2 + mlogm + mk1), where m is the number of fragments and n is the number of SNP sites. In practical biological applications, the algorithm solves the MLF problem efficiently even if m and n are large.

MOTIVATION: In genetic studies of complex diseases, haplotypes provide more information than genotypes. However, haplotyping is much more difficult than genotyping using biological techniques. Therefore effective computational techniques have been in demand. The individual haplotyping problem is the computational problem of inducing a pair of haplotypes from an individual's aligned SNP fragments. Based on various optimal criteria and including different extra information, many models for the problem have been proposed. Higher accuracy of the models has been an important issue in the study of haplotype reconstruction. RESULTS: The current article proposes a highly accurate model for the single individual haplotyping problem based on weighted fragments and genotypes with errors. The model is proved to be NP-hard even with gapless fragments. Based on the characteristics of Single Nucleotide Polymorphism (SNP) fragments, a parameterized algorithm of time complexity O(nk(2)2(k(2)) + m log m + mk(1)) is developed, where m is the number of fragments, n is the number of SNP sites, k(1) is the maximum number of SNP sites that a fragment covers (no more than n and usually smaller than 10) and k(2) is the maximum number of the fragments covering a SNP site (usually no more than 19). Extensive experiments show that this model is more accurate in haplotype reconstruction than other models. AVAILABILITY: The program of the parameterized algorithm can be obtained by sending an email to the corresponding author.