ALBERT

Description: Phylogenetic tree reconciliation is an important technique for reconstructing the evolutionary histories of species and genes and other dependent entities. Reconciliation is typically performed in a maximum parsimony framework and the number of optimal reconciliations can grow exponentially with the size of the trees, making it difficult to understand the solution space. This paper demonstrates how a small number of reconciliations can be found that collectively contain the most highly supported events in the solution space. While we show that the formal problem is NP-complete, we give a $1-frac{1}{e}$ approximation algorithm, experimental results that indicate its effectiveness, and the new DTL-RnB software tool that uses our algorithms to summarize the space of optimal reconciliations ( www.cs.hmc.edu/dtlrnb ).

Description: We propose a methodology for model-based fault detection and diagnosis for stochastic Boolean dynamical systems indirectly observed through a single time series of transcriptomic measurements using Next Generation Sequencing (NGS) data. The fault detection consists of an innovations filter followed by a fault certification step, and requires no knowledge about the possible system faults. The innovations filter uses the optimal Boolean state estimator, called the Boolean Kalman Filter (BKF). In the presence of knowledge about the possible system faults, we propose an additional step of fault diagnosis based on a multiple model adaptive estimation (MMAE) method consisting of a bank of BKFs running in parallel. Performance is assessed by means of false detection and misdiagnosis rates, as well as average times until correct detection and diagnosis. The efficacy of the proposed methodology is demonstrated via numerical experiments using a p53-MDM2 negative feedback loop Boolean network with stuck-at faults that model molecular events commonly found in cancer.

Description: New de novo transcriptome assembly and annotation methods provide an incredible opportunity to study the transcriptome of organisms that lack an assembled and annotated genome. There are currently a number of de novo transcriptome assembly methods, but it has been difficult to evaluate the quality of these assemblies. In order to assess the quality of the transcriptome assemblies, we composed a workflow of multiple quality check measurements that in combination provide a clear evaluation of the assembly performance. We presented novel transcriptome assemblies and functional annotations for Pacific Whiteleg Shrimp ( Litopenaeus vannamei ), a mariculture species with great national and international interest, and no solid transcriptome/genome reference. We examined Pacific Whiteleg transcriptome assemblies via multiple metrics, and provide an improved gene annotation. Our investigations show that assessing the quality of an assembly purely based on the assembler's statistical measurements can be misleading; we propose a hybrid approach that consists of statistical quality checks and further biological-based evaluations.

Description: Hi-C technology, a chromosome conformation capture (3C) based method, has been developed to capture genome-wide interactions at a given resolution. The next challenge is to reconstruct 3D structure of genome from the 3C-derived data computationally. Several existing methods have been proposed to obtain a consensus structure or ensemble structures. These methods can be categorized as probabilistic models or restraint-based models. In this paper, we propose a method, named ShRec3D+, to infer a consensus 3D structure of a genome from Hi-C data. The method is a two-step algorithm which is based on ChromSDE and ShRec3D methods. First, correct the conversion factor by golden section search for converting interaction frequency data to a distance weighted graph. Second, apply shortest-path algorithm and multi-dimensional scaling (MDS) algorithm to compute the 3D coordinates of a set of genomic loci from the distance graph. We validate ShRec3D+ accuracy on both simulation data and publicly Hi-C data. Our test results indicate that our method successfully corrects the parameter with a given resolution, is more accurate than ShRec3D, and is more efficient and robust than ChromSDE.

Description: Determining gender by examining the human brain is not a simple task because the spatial structure of the human brain is complex, and no obvious differences can be seen by the naked eyes. In this paper, we propose a novel three-dimensional feature descriptor, the three-dimensional weighted histogram of gradient orientation (3D WHGO) to describe this complex spatial structure. The descriptor combines local information for signal intensity and global three-dimensional spatial information for the whole brain. We also improve a framework to address the classification of three-dimensional images based on MRI. This framework, three-dimensional spatial pyramid, uses additional information regarding the spatial relationship between features. The proposed method can be used to distinguish gender at the individual level. We examine our method by using the gender identification of individual magnetic resonance imaging (MRI) scans of a large sample of healthy adults across four research sites, resulting in up to individual-level accuracies under the optimized parameters for distinguishing between females and males. Compared with previous methods, the proposed method obtains higher accuracy, which suggests that this technology has higher discriminative power. With its improved performance in gender identification, the proposed method may have the potential to inform clinical practice and aid in research on neurological and psychiatric disorders.

Description: Ultra-high dimensional variable selection has become increasingly important in analysis of neuroimaging data. For example, in the Autism Brain Imaging Data Exchange (ABIDE) study, neuroscientists are interested in identifying important biomarkers for early detection of the autism spectrum disorder (ASD) using high resolution brain images that include hundreds of thousands voxels. However, most existing methods are not feasible for solving this problem due to their extensive computational costs. In this work, we propose a novel multiresolution variable selection procedure under a Bayesian probit regression framework. It recursively uses posterior samples for coarser-scale variable selection to guide the posterior inference on finer-scale variable selection, leading to very efficient Markov chain Monte Carlo (MCMC) algorithms. The proposed algorithms are computationally feasible for ultra-high dimensional data. Also, our model incorporates two levels of structural information into variable selection using Ising priors: the spatial dependence between voxels and the functional connectivity between anatomical brain regions. Applied to the resting state functional magnetic resonance imaging (R-fMRI) data in the ABIDE study, our methods identify voxel-level imaging biomarkers highly predictive of the ASD, which are biologically meaningful and interpretable. Extensive simulations also show that our methods achieve better performance in variable selection compared to existing methods.

Description: In systems neuroscience, it is becoming increasingly common to record the activity of hundreds of neurons simultaneously via electrode arrays. The ability to accurately measure the causal interactions among multiple neurons in the brain is crucial to understanding how neurons work in concert to generate specific brain functions. The development of new statistical methods for assessing causal influence between spike trains is still an active field of neuroscience research. Here, we suggest a copula-based Granger causality measure for the analysis of neural spike train data. This method is built upon our recent work on copula Granger causality for the analysis of continuous-valued time series by extending it to point-process neural spike train data. The proposed method is therefore able to reveal nonlinear and high-order causality in the spike trains while retaining all the computational advantages such as model-free, efficient estimation, and variability assessment of Granger causality. The performance of our algorithm can be further boosted with time-reversed data. Our method performed well on extensive simulations, and was then demonstrated on neural activity simultaneously recorded from primary visual cortex of a monkey performing a contour detection task.

Description: The focus of this paper is the frequent gene team problem. Given a quorum parameter μ and a set of m genomes, the problem is to find gene teams that occur in at least μ of the given genomes. In this paper, a new algorithm is presented. Previous solutions are efficient only when μ is small. Unlike previous solutions, the presented algorithm does not rely on examining every combination of μ genomes. Its time complexity is independent of μ. Under some realistic assumptions, the practical running time is estimated to be $O(m^{2}n^{2}; {mathrm{lg}};n)$ , where n is the maximum length of the input genomes. Experiments showed that the presented algorithm is extremely efficient. For any μ, it takes less than 1 second to process 100 bacterial genomes and takes only 10 minutes to process 2,000 genomes. The presented algorithm can be used as an effective tool for large scale genome analyses.

Description: In this era of genome-wide association studies (GWAS), the quest for understanding the genetic architecture of complex diseases is rapidly increasing more than ever before. The development of high throughput genotyping and next generation sequencing technologies enables genetic epidemiological analysis of large scale data. These advances have led to the identification of a number of single nucleotide polymorphisms (SNPs) responsible for disease susceptibility. The interactions between SNPs associated with complex diseases are increasingly being explored in the current literature. These interaction studies are mathematically challenging and computationally complex. These challenges have been addressed by a number of data mining and machine learning approaches. This paper reviews the current methods and the related software packages to detect the SNP interactions that contribute to diseases. The issues that need to be considered when developing these models are addressed in this review. The paper also reviews the achievements in data simulation to evaluate the performance of these models. Further, it discusses the future of SNP interaction analysis.

Description: Motifs in complex biological, technological, and social networks, or in other types of networks are connected to patterns that occur at significantly higher frequency compared to similar random networks. Finding motifs helps scientists to know more about networks’ structure and function, and this goal cannot be achieved without efficient algorithms. Existing methods for counting network motifs are extremely costly in CPU time and memory consumption. In addition, they restrict to the larger motifs. In this paper, a new algorithm called FraMo is presented based on ‘fractal theory’. This method consists of three phases: at first, a complex network is converted to a multifractal network. Then, using maximum likelihood estimation, distribution parameters is estimated for the multifractal network, and at last the approximate number of network motifs is calculated. Experimental results on several benchmark datasets show that our algorithm can efficiently approximate the number of motifs in any size in undirected networks and compare its performance favorably with similar existing algorithms in terms of CPU time and memory usage.

Description: Regions of interest (ROIs) based classification has been widely investigated for analysis of brain magnetic resonance imaging (MRI) images to assist the diagnosis of Alzheimer's disease (AD) including its early warning and developing stages, e.g., mild cognitive impairment (MCI) including MCI converted to AD (MCIc) and MCI not converted to AD (MCInc). Since an ROI representation of brain structures is obtained either by pre-definition or by adaptive parcellation, the corresponding ROI in different brains can be measured. However, due to noise and small sample size of MRI images, representations generated from single or multiple ROIs may not be sufficient to reveal the underlying anatomical differences between the groups of disease-affected patients and health controls (HC). In this paper, we employ a whole brain hierarchical network (WBHN) to represent each subject. The whole brain of each subject is divided into 90, 54, 14, and 1 regions based on Automated Anatomical Labeling (AAL) atlas. The connectivity between each pair of regions is computed in terms of Pearson's correlation coefficient and used as classification feature. Then, to reduce the dimensionality of features, we select the features with higher $F-$ scores. Finally, we use multiple kernel boosting (MKBoost) algorithm to perform the classification. Our proposed method is evaluated on MRI images of 710 subjects (200 AD, 120 MCIc, 160 MCInc, and 230 HC) from the Alzheimer's Disease Neuroimaging Initiative (ADNI) database. The experimental results show that our proposed method achieves an accuracy of 94.65 percent and an area under the receiver operating characteristic (ROC) curve (AUC) of 0.954 for AD/HC classification, an accuracy of 89.63 percent and an AUC of 0.907 for AD/MCI classification, an- accuracy of 85.79 percent and an AUC of 0.826 for MCI/HC classification, and an accuracy of 72.08 percent and an AUC of 0.716 for MCIc/MCInc classification, respectively. Our results demonstrate that our proposed method is efficient and promising for clinical applications for the diagnosis of AD via MRI images.

Description: Enumeration of chemical structures is useful for drug design, which is one of the main targets of computational biology and bioinformatics. A chemical graph $G$ with no other cycles than benzene rings is called tree-like , and becomes a tree $T$ possibly with multiple edges if we contract each benzene ring into a single virtual atom of valence 6. All tree-like chemical graphs with a given tree representation $T$ are called the substituted benzene isomers of $T$ . When we replace each virtual atom in $T$ with a benzene ring to obtain a substituted benzene isomer, distinct isomers of $T$ are caused by the difference in arrangements of atom groups around a benzene ring. In this paper, we propose an efficient algorithm that enumerates all substituted benzene isomers of a given tree representation $T$ . Our algorithm first counts the number

Description: Determining the dynamics of pathways associated with cancer progression is critical for understanding the etiology of diseases. Advances in biological technology have facilitated the simultaneous genomic profiling of multiple patients at different clinical stages, thus generating the dynamic genomic data for cancers. Such data provide enable investigation of the dynamics of related pathways. However, methods for integrative analysis of dynamic genomic data are inadequate. In this study, we develop a novel nonnegative matrix factorization algorithm for dynamic modules ( NMF-DM ), which simultaneously analyzes multiple networks for the identification of stage-specific and dynamic modules. NMF-DM applies the temporal smoothness framework by balancing the networks at the current stage and the previous stage. Experimental results indicate that the NMF-DM algorithm is more accurate than the state-of-the-art methods in artificial dynamic networks. In breast cancer networks, NMF-DM reveals the dynamic modules that are important for cancer stage transitions. Furthermore, the stage-specific and dynamic modules have distinct topological and biochemical properties. Finally, we demonstrate that the stage-specific modules significantly improve the accuracy of cancer stage prediction. The proposed algorithm provides an effective way to explore the time-dependent cancer genomic data.

Description: MicroRNAs (miRNAs) are known as an important indicator of cancers. The presence of cancer can be detected by identifying the responsible miRNAs. A fuzzy-rough entropy measure (FREM) is developed which can rank the miRNAs and thereby identify the relevant ones. FREM is used to determine the relevance of a miRNA in terms of separability between normal and cancer classes. While computing the FREM for a miRNA, fuzziness takes care of the overlapping between normal and cancer expressions, whereas rough lower approximation determines their class sizes. MiRNAs are sorted according to the highest relevance (i.e., the capability of class separation) and a percentage among them is selected from the top ranked ones. FREM is also used to determine the redundancy between two miRNAs and the redundant ones are removed from the selected set, as per the necessity. A histogram based patient selection method is also developed which can help to reduce the number of patients to be dealt during the computation of FREM, while compromising very little with the performance of the selected miRNAs for most of the data sets. The superiority of the FREM as compared to some existing methods is demonstrated extensively on six data sets in terms of sensitivity, specificity, and $F$ score. While for these data sets the $F$ score of the miRNAs selected by our method varies from 0.70 to 0.91 using SVM, those results vary from 0.37 to 0.90 for some other methods. Moreover, all the selected miRNAs corroborate with the findings of biological investigations or pathway analysis tools. The source code of FREM is available at http://www.jayanta.droppages.com/FREM.html .

Description: Identification of combinatorial markers from multiple data sources is a challenging task in bioinformatics. Here, we propose a novel computational framework for identifying significant combinatorial markers ( $SCM$ s) using both gene expression and methylation data. The gene expression and methylation data are integrated into a single continuous data as well as a (post-discretized) boolean data based on their intrinsic (i.e., inverse) relationship. A novel combined score of methylation and expression data (viz., $CoMEx$ ) is introduced which is computed on the integrated continuous data for identifying initial non-redundant set of genes. Thereafter, (maximal) frequent closed homogeneous genesets are identified using a well-known biclustering algorithm applied on the integrated boolean data of the determined non-redundant set of genes. A novel sample-based weighted support ( $WS$ ) is then proposed that is consecutively calculated on the integrated boolean data of the determined non-redundant set of genes in order to identify the non-redundant significant genesets. The top few resulting genesets are identified as potential $SCM$ s. Since our proposed method generates a smaller number of significant non-redundant genesets than those by other popular methods, the method is much faster than the others. Application of the proposed techniq- e on an expression and a methylation data for Uterine tumor or Prostate Carcinoma produces a set of significant combination of markers. We expect that such a combination of markers will produce lower false positives than individual markers.

Description: A minimum hybridization network is a rooted phylogenetic network that displays two given rooted phylogenetic trees using a minimum number of reticulations. Previous mathematical work on their calculation has usually assumed the input trees to be bifurcating, correctly rooted, or that they both contain the same taxa. These assumptions do not hold in biological studies and “realistic” trees have multifurcations, are difficult to root, and rarely contain the same taxa. We present a new algorithm for computing minimum hybridization networks for a given pair of “realistic” rooted phylogenetic trees. We also describe how the algorithm might be used to improve the rooting of the input trees. We introduce the concept of “autumn trees”, a nice framework for the formulation of algorithms based on the mathematics of “maximum acyclic agreement forests”. While the main computational problem is hard, the run-time depends mainly on how different the given input trees are. In biological studies, where the trees are reasonably similar, our parallel implementation performs well in practice. The algorithm is available in our open source program Dendroscope 3, providing a platform for biologists to explore rooted phylogenetic networks. We demonstrate the utility of the algorithm using several previously studied data sets.

Description: The human colorectal carcinoma cell line (Caco-2) is a commonly used in-vitro test that predicts the absorption potential of orally administered drugs. In-silico prediction methods, based on the Caco-2 assay data, may increase the effectiveness of the high-throughput screening of new drug candidates. However, previously developed in-silico models that predict the Caco-2 cellular permeability of chemical compounds use handcrafted features that may be dataset-specific and induce over-fitting problems. Deep Neural Network (DNN) generates high-level features based on non-linear transformations for raw features, which provides high discriminant power and, therefore, creates a good generalized model. We present a DNN-based binary Caco-2 permeability classifier. Our model was constructed based on 663 chemical compounds with in-vitro Caco-2 apparent permeability data. Two hundred nine molecular descriptors are used for generating the high-level features during DNN model generation. Dropout regularization is applied to solve the over-fitting problem and the non-linear activation. The Rectified Linear Unit (ReLU) is adopted to reduce the vanishing gradient problem. The results demonstrate that the high-level features generated by the DNN are more robust than handcrafted features for predicting the cellular permeability of structurally diverse chemical compounds in Caco-2 cell lines.

Description: Read trimming is a fundamental first step of the analysis of next generation sequencing (NGS) data. Traditionally, it is performed heuristically, and algorithmic work in this area has been neglected. Here, we address this topic and formulate three optimization problems for block-based trimming (truncating the same low-quality positions at both ends for all reads and removing low-quality truncated reads). We find that all problems are NP-hard. Hence, we investigate the approximability of the problems. Two of them are NP-hard to approximate. However, the non-random distribution of quality scores in NGS data sets makes it tempting to speculate that quality constraints for read positions are typically satisfied by fulfilling quality constraints for reads. Thus, we propose three relaxed problems and develop efficient polynomial-time algorithms for them including heuristic speed-up techniques and parallelizations. We apply these optimized block trimming algorithms to 12 data sets from three species, four sequencers, and read lengths ranging from 36 to 101 bp and find that (i) the omitted constraints are indeed almost always satisfied, (ii) the optimized read trimming algorithms typically yield a higher number of untrimmed bases than traditional heuristics, and (iii) these results can be generalized to alternative objective functions beyond counting the number of untrimmed bases.

Description: Advances in de novo synthesis of DNA and computational gene design methods make possible the customization of genes by direct manipulation of features such as codon bias and mRNA secondary structure. Codon context is another feature significantly affecting mRNA translational efficiency, but existing methods and tools for evaluating and designing novel optimized protein coding sequences utilize untested heuristics and do not provide quantifiable guarantees on design quality. In this study we examine statistical properties of codon context measures in an effort to better understand the phenomenon. We analyze the computational complexity of codon context optimization and design exact and efficient heuristic gene recoding algorithms under reasonable constraint models. We also present a web-based tool for evaluating codon context bias in the appropriate context.

Description: To assess the genetic diversity of an environmental sample in metagenomics studies, the amplicon sequences of 16s rRNA genes need to be clustered into operational taxonomic units (OTUs). Many existing tools for OTU clustering trade off between accuracy and computational efficiency. We propose a novel OTU clustering algorithm, hc-OTU, which achieves high accuracy and fast runtime by exploiting homopolymer compaction and k-mer profiling to significantly reduce the computing time for pairwise distances of amplicon sequences. We compare the proposed method with other widely used methods, including UCLUST, CD-HIT, MOTHUR, ESPRIT, ESPRIT-TREE, and CLUSTOM, comprehensively, using nine different experimental datasets and many evaluation metrics, such as normalized mutual information, adjusted Rand index, measure of concordance, and F-score. Our evaluation reveals that the proposed method achieves a level of accuracy comparable to the respective accuracy levels of MOTHUR and ESPRIT-TREE, two widely used OTU clustering methods, while delivering orders-of-magnitude speedups.

Description: Recent studies have suggested abnormal brain network organization in subjects with Autism Spectrum Disorders (ASD). Here we applied spectral clustering algorithm, diverse centrality measures (betweenness (BC), clustering (CC), eigenvector (EC), and degree (DC)), and also the network entropy (NE) to identify brain sub-systems associated with ASD. We have found that BC increases in the following ASD clusters: in the somatomotor, default-mode, cerebellar, and fronto-parietal. On the other hand, CC, EC, and DC decrease in the somatomotor, default-mode, and cerebellar clusters. Additionally, NE decreases in ASD in the cerebellar cluster. These findings reinforce the hypothesis of under-connectivity in ASD and suggest that the difference in the network organization is more prominent in the cerebellar system. The cerebellar cluster presents reduced NE in ASD, which relates to a more regular organization of the networks. These results might be important to improve current understanding about the etiological processes and the development of potential tools supporting diagnosis and therapeutic interventions.

Description: Probabilistic models have been successfully adopted in computational biology and bioinformatics. Recently, a number of powerful probabilistic models and methods have been developed in the field of computational neuroscience, and these effective models have significantly advanced this field. This special section aims to capture some snapshots of recent developments of probabilistic methods in the synergistic combinations of cognitive brain science, brain imaging, and neuroscience. It aims to report the latest advances in these fields to the research community working on probabilistic methods in brain imaging analysis and computational neuroscience. This special section includes five contributed articles.

Description: Parkinson's disease (PD) is a progressive neurodegenerative disorder characterized clinically by motor dysfunction (bradykinesia, rigidity, tremor, and postural instability), and pathologically by the loss of dopaminergic neurons in the substantia nigra of the basal ganglia. Growing literature supports that cognitive deficits may also be present in PD, even in non-demented patients. Gray matter (GM) atrophy has been reported in PD and may be related to cognitive decline. This study investigated cortical thickness in non-demented PD subjects and elucidated its relationship to cognitive impairment using high-resolution T1-weighted brain MRI and comprehensive cognitive function scores from 71 non-demented PD and 48 control subjects matched for age, gender, and education. Cortical thickness was compared between groups using a flexible hierarchical multivariate Bayesian model, which accounts for correlations between brain regions. Correlation analyses were performed among brain areas and cognitive domains as well, which showed significant group differences in the PD population. Compared to Controls, PD subjects demonstrated significant age-adjusted cortical thinning predominantly in inferior and superior parietal areas and extended to superior frontal, superior temporal, and precuneus areas (posterior probability >0.9). Cortical thinning was also found in the left precentral and lateral occipital, and right postcentral, middle frontal, and fusiform regions (posterior probability >0.9). PD patients showed significantly reduced cognitive performance in executive function, including set shifting (p = 0.005) and spontaneous flexibility (p = 0.02), which were associated with the above cortical thinning regions (p 〈 0.05).

Description: This special section of the IEEE/ACM Transactions on Computational Biology and Bioinformatics contains extended versions of the best papers presented at the First International Conference on Algorithms for Computational Biology (AlCoB 2014). Out of 39 submissions to the conference, only four papers representing the current state-of-the-art in their respective domains were accepted to this special section.

Description: Genome Rearrangements are large-scale mutational events that affect genomes during the evolutionary process. Therefore, these mutations differ from punctual mutations. They can move genes from one place to the other, change the orientation of some genes, or even change the number of chromosomes. In this work, we deal with inversion events which occur when a segment of DNA sequence in the genome is reversed. In our model, each inversion costs the number of elements in the reversed segment. We present a new algorithm for this problem based on the metaheuristic called Greedy Randomized Adaptive Search Procedure (GRASP) that has been routinely used to find solutions for combinatorial optimization problems. In essence, we implemented an iterative process in which each iteration receives a feasible solution whose neighborhood is investigated. Our analysis shows that we outperform any other approach by significant margin. We also use our algorithm to build phylogenetic trees for a subset of species in the Yersinia genus and we compared our trees to other results in the literature.

Description: The endoplasmic reticulum (ER) is an intricate network that pervades the entire cortex of plant cells and its geometric shape undergoes drastic changes. This paper proposes a mathematical model to reconstruct geometric network dynamics by combining the node movements within the network and topological changes engendered by these nodes. The network topology in the model is determined by a modified optimization procedure from the work (Lemarchand, et al. 2014) which minimizes the total length taking into account both degree and angle constraints, beyond the conditions of connectedness and planarity. A novel feature for solving our optimization problem is the use of “lifted” angle constraints, which allows one to considerably reduce the solution runtimes. Using this optimization technique and a Langevin approach for the branching node movement, the simulated network dynamics represent the ER network dynamics observed under latrunculin B treated condition and recaptures features such as the appearance/disappearance of loops within the ER under the native condition. The proposed modeling approach allows quantitative comparison of networks between the model and experimental data based on topological changes induced by node dynamics. An increased temporal resolution of experimental data will allow a more detailed comparison of network dynamics using this modeling approach.

Description: Reconstruction of ancestral relationships among genera, species, and populations is a core task in evolutionary biology. At the population level, pedigrees have been commonly used. Reconstruction of pedigree is required in practice due to legal or medical reasons. Pedigrees are very important to geneticists for inferring haplotype segments, recombination, and allele sharing status with which disease loci can be identified. Evaluating reconstruction methods requires comparing the inferred pedigree and the known pedigrees. Moreover, comparison of pedigrees is required in studying relationships among crops such as maize, wheat and barley, etc. In this paper, we discuss three models for comparison of pedigrees, the maximum pedigree isomorphism problem, the maximum paternal-path-preserved mapping problem, and the minimum edge-cutting mapping problem. For the maximum pedigree isomorphism problem, we prove that the problem is NP-hard and give a fixed-parameter algorithm for the problem. For the maximum paternal-path-preserved mapping problem, we give a dynamic-programming algorithm to find the mapping that preserves the maximum number of paternal paths between the two input pedigrees. For the minimum edge-cutting mapping problem, we prove that the problem is NP-hard and give a fixed-parameter algorithm with running time $O(n(1+sqrt{2})^k)$ , where $n$ is the number of vertices in the two input pedigrees and $k$ is the number of edges to be cut. This algorithm is useful in practice when comparing two similar pedigrees.

Description: Network component analysis (NCA) is an important method for inferring transcriptional regulatory networks (TRNs) and recovering transcription factor activities (TFAs) using gene expression data, and the prior information about the connectivity matrix. The algorithms currently available crucially depend on the completeness of this prior information. However, inaccuracies in the measurement process may render incompleteness in the available knowledge about the connectivity matrix. Hence, computationally efficient algorithms are needed to overcome the possible incompleteness in the available data. We present a sparse network component analysis algorithm (sparseNCA), which incorporates the effect of incompleteness in the estimation of TRNs by imposing an additional sparsity constraint using the $ell _1$ norm, which results in a greater estimation accuracy. In order to improve the computational efficiency, an iterative re-weighted $ell _2$ method is proposed for the NCA problem which not only promotes sparsity but is hundreds of times faster than the $ell _1$ norm based solution. The performance of sparseNCA is rigorously compared to that of FastNCA and NINCA using synthetic data as well as real data. It is shown that sparseNCA outperforms the existing state-of-the-art algorithms both in terms of estimation accuracy and consistency with the added advantage of low computational complexity. The performance of sparseNCA compared to its predecessors is particularly pronounced in case of incomplete prior info- mation about the sparsity of the network. Subnetwork analysis is performed on the E.coli data which reiterates the superior consistency of the proposed algorithm.

Description: Differential gene expression testing is an analysis commonly applied to RNA-Seq data. These statistical tests identify genes that are significantly different across phenotypes. We extend this testing paradigm to multivariate gene interactions from a classification perspective with the goal to detect novel gene interactions for the phenotypes of interest. This is achieved through our novel computational framework comprised of a hierarchical statistical model of the RNA-Seq processing pipeline and the corresponding optimal Bayesian classifier. Through Markov Chain Monte Carlo sampling and Monte Carlo integration, we compute quantities where no analytical formulation exists. The performance is then illustrated on an expression dataset from a dietary intervention study where we identify gene pairs that have low classification error yet were not identified as differentially expressed. Additionally, we have released the software package to perform OBC classification on RNA-Seq data under an open source license and is available at http://bit.ly/obc_package .

Description: Fusarium verticillioides is a fungal pathogen that triggers stalk rots and ear rots in maize. In this study, we performed a comparative analysis of wild type and loss-of-virulence mutant F. verticillioides co-expression networks to identify subnetwork modules that are associated with its pathogenicity. We constructed the F. verticillioides co-expression networks from RNA-Seq data and searched through these networks to identify subnetwork modules that are differentially activated between the wild type and mutant F. verticillioides , which considerably differ in terms of pathogenic potentials. A greedy seed-and-extend approach was utilized in our search, where we also used an efficient branch-out technique for reliable prediction of functional subnetwork modules in the fungus. Through our analysis, we identified four potential pathogenicity-associated subnetwork modules, each of which consists of interacting genes with coordinated expression patterns, but whose activation level is significantly different in the wild type and the mutant. The predicted modules were comprised of functionally coherent genes and topologically cohesive. Furthermore, they contained several orthologs of known pathogenic genes in other fungi, which may play important roles in the fungal pathogenesis.

Description: N6-Methyladenosine (m 6 A) transcriptome methylation is an exciting new research area that just captures the attention of research community. We present in this paper, MeTDiff, a novel computational tool for predicting differential m 6 A methylation sites from Methylated RNA immunoprecipitation sequencing (MeRIP-Seq) data. Compared with the existing algorithm exomePeak, the advantages of MeTDiff are that it explicitly models the reads variation in data and also devices a more power likelihood ratio test for differential methylation site prediction. Comprehensive evaluation of MeTDiff's performance using both simulated and real datasets showed that MeTDiff is much more robust and achieved much higher sensitivity and specificity over exomePeak. The R package “MeTDiff” and additional details are available at: https://github.com/compgenomics/MeTDiff .

Description: Neglected tropical diseases, especially those caused by helminths, constitute some of the most common infections of the world's poorest people. Amongst these, schistosomiasis (bilharzia or ‘snail fever’), caused by blood flukes of the genus Schistosoma, ranks second only to malaria in terms of human impact: two hundred million people are infected and close to 800 million are at risk of infection. Drug screening against helminths poses unique challenges: the parasite cannot be cloned and is difficult to target using gene knockouts or RNAi. Consequently, both lead identification and validation involve phenotypic screening, where parasites are exposed to compounds whose effects are determined through the analysis of the ensuing phenotypic responses. The efficacy of leads thus identified derives from one or more or even unknown molecular mechanisms of action. The two most immediate and significant challenges that confront the state-of-the-art in this area are: the development of automated and quantitative phenotypic screening techniques and the mapping and quantitative characterization of the totality of phenotypic responses of the parasite. In this paper, we investigate and propose solutions for the latter problem in terms of the following: (1) mathematical formulation and algorithms that allow rigorous representation of the phenotypic response space of the parasite, (2) application of graph-theoretic and network analysis techniques for quantitative modeling and characterization of the phenotypic space, and (3) application of the aforementioned methodology to analyze the phenotypic space of S. mansoni – one of the etiological agents of schistosomiasis, induced by compounds that target its polo-like kinase 1 (PLK 1) gene – a recently validated drug target. In our approach, first, bio-image analysis algorithms are used to quantify the phenotypic responses of d- fferent drugs. Next, these responses are linearly mapped into a low- dimensional space using Principle Component Analysis (PCA). The phenotype space is modeled using neighborhood graphs which are used to represent the similarity amongst the phenotypes. These graphs are characterized and explored using network analysis algorithms. We present a number of results related to both the nature of the phenotypic space of the S. mansoni parasite as well as algorithmic issues encountered in constructing and analyzing the phenotypic-response space. In particular, the phenotype distribution of the parasite was found to have a distinct shape and topology. We have also quantitatively characterized the phenotypic space by varying critical model parameters. Finally, these maps of the phenotype space allows visualization and reasoning about complex relationships between putative drugs and their system-wide effects and can serve as a highly efficient paradigm for assimilating and unifying information from phenotypic screens both during lead identification and lead optimization.

Description: Smoking is the major cause of lung cancer and the leading cause of cancer-related death in the world. The most current view about lung cancer is no longer limited to individual genes being mutated by any carcinogenic insults from smoking. Instead, tumorigenesis is a phenotype conferred by many systematic and global alterations, leading to extensive heterogeneity and variation for both the genotypes and phenotypes of individual cancer cells. Thus, strategically it is foremost important to develop a methodology to capture any consistent and global alterations presumably shared by most of the cancerous cells for a given population. This is particularly true that almost all of the data collected from solid cancers (including lung cancers) are usually distant apart over a large span of temporal or even spatial contexts. Here, we report a multiple non-Gaussian graphical model to reconstruct the gene interaction network using two previously published gene expression datasets. Our graphical model aims to selectively detect gross structural changes at the level of gene interaction networks. Our methodology is extensively validated, demonstrating good robustness, as well as the selectivity and specificity expected based on our biological insights. In summary, gene regulatory networks are still relatively stable during presumably the early stage of neoplastic transformation. But drastic structural differences can be found between lung cancer and its normal control, including the gain of functional modules for cellular proliferations such as EGFR and PDGFRA, as well as the lost of the important IL6 module, supporting their roles as potential drug targets. Interestingly, our method can also detect early modular changes, with the ALDH3A1 and its associated interactions being strongly implicated as a potential early marker, whose activations appear to alter LCN2 module as well as its interactions with the important TP53-MDM2 circuitry. Our strategy using the graphical model to re- onstruct gene interaction work with biologically-inspired constraints exemplifies the importance and beauty of biology in developing any bio-computational approach.

Description: The application of machine learning methods for the identification of candidate genes responsible for phenotypes of interest, such as cancer, is a major challenge in the field of bioinformatics. These lists of genes are often called genomic signatures and their linkage to phenotype associations may form a significant step in discovering the causation between genotypes and phenotypes. Traditional methods that produce genomic signatures from DNA Microarray data tend to extract significantly different lists under relatively small variations of the training data. That instability hinders the validity of research findings and raises skepticism about the reliability of such methods. In this study, a complete framework for the extraction of stable and reliable lists of candidate genes is presented. The proposed methodology enforces stability of results at the validation step and as a result, it is independent of the feature selection and classification methods used. Furthermore, two different statistical tests are performed in order to assess the statistical significance of the observed results. Moreover, the consistency of the signatures extracted by independent executions of the proposed method is also evaluated. The results of this study highlight the importance of stability issues in genomic signatures, beyond their prediction capabilities.

Description: Heme is an essential biomolecule that widely exists in numerous extant organisms. Accurately identifying heme binding residues (HEMEs) is of great importance in disease progression and drug development. In this study, a novel predictor named HEMEsPred was proposed for predicting HEMEs. First, several sequence- and structure-based features, including amino acid composition, motifs, surface preferences, and secondary structure, were collected to construct feature matrices. Second, a novel fast-adaptive ensemble learning scheme was designed to overcome the serious class-imbalance problem as well as to enhance the prediction performance. Third, we further developed ligand-specific models considering that different heme ligands varied significantly in their roles, sizes, and distributions. Statistical test proved the effectiveness of ligand-specific models. Experimental results on benchmark datasets demonstrated good robustness of our proposed method. Furthermore, our method also showed good generalization capability and outperformed many state-of-art predictors on two independent testing datasets. HEMEsPred web server was available at http://www.inforstation.com/HEMEsPred/ for free academic use.

Description: When a gene shows varying levels of expression among normal people but similar levels in disease patients or shows similar levels of expression among normal people but different levels in disease patients, we can assume that the gene is associated with the disease. By utilizing this gene expression heterogeneity, we can obtain additional information that abets discovery of disease-associated genes. In this study, we used collaborative filtering to calculate the degree of gene expression heterogeneity between classes and then scored the genes on the basis of the degree of gene expression heterogeneity to find “differentially predicted” genes. Through the proposed method, we discovered more prostate cancer-associated genes than 10 comparable methods. The genes prioritized by the proposed method are potentially significant to biological processes of a disease and can provide insight into them.

Description: Rooted phylogenetic networks are used to describe evolutionary histories that contain non-treelike evolutionary events such as hybridization and horizontal gene transfer. In some cases, such histories can be described by a phylogenetic base-tree with additional linking arcs, which can, for example, represent gene transfer events. Such phylogenetic networks are called tree-based . Here, we consider two possible generalizations of this concept to nonbinary networks, which we call tree-based and strictly-tree-based nonbinary phylogenetic networks. We give simple graph-theoretic characterizations of tree-based and strictly-tree-based nonbinary phylogenetic networks. Moreover, we show for each of these two classes that it can be decided in polynomial time whether a given network is contained in the class. Our approach also provides a new view on tree-based binary phylogenetic networks. Finally, we discuss two examples of nonbinary phylogenetic networks in biology and show how our results can be applied to them.

Description: Many discrete mathematics problems in phylogenetics are defined in terms of the relative labeling of pairs of leaf-labeled trees. These relative labelings are naturally formalized as tanglegrams, which have previously been an object of study in coevolutionary analysis. Although there has been considerable work on planar drawings of tanglegrams, they have not been fully explored as combinatorial objects until recently. In this paper, we describe how many discrete mathematical questions on trees “factor” through a problem on tanglegrams, and how understanding that factoring can simplify analysis. Depending on the problem, it may be useful to consider a unordered version of tanglegrams, and/or their unrooted counterparts. For all of these definitions, we show how the isomorphism types of tanglegrams can be understood in terms of double cosets of the symmetric group, and we investigate their automorphisms. Understanding tanglegrams better will isolate the distinct problems on leaf-labeled pairs of trees and reveal natural symmetries of spaces associated with such problems.

Description: This index covers all technical items - papers, correspondence, reviews, etc. - that appeared in this periodical during the year, and items from previous years that were commented upon or corrected in this year. Departments and other items may also be covered if they have been judged to have archival value. The Author Index contains the primary entry for each item, listed under the first author's name. The primary entry includes the co-authors' names, the title of the paper or other item, and its location, specified by the publication abbreviation, year, month, and inclusive pagination. The Subject Index contains entries describing the item under all appropriate subject headings, plus the first author's name, the publication abbreviation, month, and year, and inclusive pages. Note that the item title is found only under the primary entry in the Author Index.

Description: This study proposes a new method to determine the functions of an unannotated protein. The proteins and amino acid residues mentioned in biomedical texts associated with an unannotated protein $p$ can be considered as characteristics terms for $p$ , which are highly predictive of the potential functions of $p$ . Similarly, proteins and amino acid residues mentioned in biomedical texts associated with proteins annotated with a functional category $f$ can be considered as characteristics terms of $f$ . We introduce in this paper an information extraction system called IFP_IFC that predicts the functions of an unannotated protein $p$ by representing $p$ and each functional category $f$ by a vector of weights. Each weight reflects the degree of association between a c- aracteristic term and $p$ (or a characteristic term and $f$ ). First, IFP_IFC constructs a network, whose nodes represent the different functional categories, and its edges the interrelationships between the nodes. Then, it determines the functions of $p$ by employing random walks with restarts on the mentioned network. The walker is the vector of $p$ . Finally, $p$ is assigned to the functional categories of the nodes in the network that are visited most by the walker. We evaluated the quality of IFP_IFC by comparing it experimentally with two other systems. Results showed marked improvement.

Description: Gene-expression-based phenotype classification is used for disease diagnosis and prognosis relating to treatment strategies. The present paper considers classification based on sequential measurements of multiple genes using gene regulatory network (GRN) modeling. There are two networks, original and mutated, and observations consist of trajectories of network states. The problem is to classify an observation trajectory as coming from either the original or mutated network. GRNs are modeled via probabilistic Boolean networks, which incorporate stochasticity at both the gene and network levels. Mutation affects the regulatory logic. Classification is based upon observing a trajectory of states of some given length. We characterize the Bayes classifier and find the Bayes error for a general PBN and the special case of a single Boolean network affected by random perturbations (BNp). The Bayes error is related to network sensitivity, meaning the extent of alteration in the steady-state distribution of the original network owing to mutation. Using standard methods to calculate steady-state distributions is cumbersome and sometimes impossible, so we provide an efficient algorithm and approximations. Extensive simulations are performed to study the effects of various factors, including approximation accuracy. We apply the classification procedure to a p53 BNp and a mammalian cell cycle PBN.

Description: Collective motion of swimmers can be detected by hydrodynamic interactions through the effective (macroscopic) viscosity. It follows from the general hydrodynamics that the effective viscosity of non-dilute random suspensions depends on the shape of particles and of their spacial probabilistic distribution. Therefore, a comparative analysis of disordered and collectively interacting particles of the bacteria shape can be done in terms of the probabilistic geometric parameters which determine the effective viscosity. In this paper, we develop a quantitative criterion to detect the collective behavior of bacteria. This criterion is based on the basic statistic moments ( $e$ -sums or generalized Eisenstein-Rayleigh sums) which characterize the high-order correlation functions. The locations and the shape of bacteria are modeled by stadiums randomly embedded in medium without overlapping. These shape models can be considered as improvement of the previous segment model. We calculate the $e$ -sums of the simulated disordered sets and of the observed experimental locations of bacteria subtilis . The obtained results show a difference between these two sets that demonstrates the collective motion of bacteria.

Description: MicroRNAs (miRNAs) play an essential role in many biological processes by regulating the target genes, especially in the initiation and development of cancers. Therefore, the identification of the miRNA-mRNA regulatory modules is important for understanding the regulatory mechanisms. Most computational methods only used statistical correlations in predicting miRNA-mRNA modules, and neglected the fact there are causal relationships between miRNAs and their target genes. In this paper, we propose a novel approach called CALM (the causal regulatory modules) to identify the miRNA-mRNA regulatory modules through integrating the causal interactions and statistical correlations between the miRNAs and their target genes. Our algorithm largely consists of three steps: it first forms the causal regulatory relationships of miRNAs and genes from gene expression profiles and detects the miRNA clusters according to the GO function information of their target genes, then expands each miRNA cluster by greedy adding (discarding) the target genes to maximize the modularity score. To show the performance of our method, we apply CALM on four datasets including EMT, breast, ovarian, and thyroid cancer and validate our results. The experiment results show that our method can not only outperform the compared method, but also achieve ideal overall performance in terms of the functional enrichment.

Description: Epidermal Growth Factor Receptor (EGFR) signaling to the Ras-MAPK pathway is implicated in the development and progression of cancer and is a major focus of targeted combination therapies. Physiochemical models have been used for identifying and testing the signal-inhibiting potential of targeted therapies; however, their application to larger multi-pathway networks is limited by the availability of experimentally-determined rate and concentration parameters. An alternate strategy for identifying and evaluating drug-targetable nodes is proposed. A physiochemical model of EGFR-Ras-MAPK signaling is implemented and calibrated to experimental data. Essential topological features of the model are converted into a Petri net and nodes that behave as siphons—a structural property of Petri nets—are identified. Siphons represent potential drug-targets since they are unrecoverable if their values fall below a threshold. Centrality measures are then used to prioritize siphons identified as candidate drug-targets. Single and multiple drug-target combinations are identified which correspond to clinically relevant drug targets and exhibit inhibition synergy in physiochemical simulations of EGF-induced EGFR-Ras-MAPK signaling. Taken together, these studies suggest that siphons and centrality analyses are a promising computational strategy to identify and rank drug-targetable nodes in larger networks as they do not require knowledge of the dynamics of the system, but rely solely on topology.

Description: In extreme cold weather, living organisms produce Antifreeze Proteins (AFPs) to counter the otherwise lethal intracellular formation of ice. Structures and sequences of various AFPs exhibit a high degree of heterogeneity, consequently the prediction of the AFPs is considered to be a challenging task. In this research, we propose to handle this arduous manifold learning task using the notion of localized processing. In particular, an AFP sequence is segmented into two sub-segments each of which is analyzed for amino acid and di-peptide compositions. We propose to use only the most significant features using the concept of information gain (IG) followed by a random forest classification approach. The proposed RAFP-Pred achieved an excellent performance on a number of standard datasets. We report a high Youden’s index (sensitivity+specificity-1) value of 0.75 on the standard independent test data set outperforming the AFP-PseAAC, AFP_PSSM, AFP-Pred, and iAFP by a margin of 0.05, 0.06, 0.14, and 0.68, respectively. The verification rate on the UniProKB dataset is found to be 83.19 percent which is substantially superior to the 57.18 percent reported for the iAFP method.

Description: Genome-wide association study (GWAS) has been widely witnessed as a powerful tool for revealing suspicious loci from various diseases. However, real world GWAS tasks always suffer from the data imbalance problem of sufficient control samples and limited case samples. This imbalance issue can cause serious biases to the result and thus leads to losses of significance for true causal markers. To tackle this problem, we proposed a computational framework to perform association correction for imbalanced data (ACID) that could potentially improve the performance of GWAS under the imbalance condition. ACID is inspired by the imbalance learning theory but is particularly modified to address the task of association discovery from sequential genomic data. Simulation studies demonstrate ACID can dramatically improve the power of traditional GWAS method on the dataset with severe imbalances. We further applied ACID to two imbalanced datasets (gastric cancer and bladder cancer) to conduct genome wide association analysis. Experimental results indicate that our method has better abilities in identifying suspicious loci than the regression approach and shows consistencies with existing discoveries.

Description: Interleukin-8 (IL-8, CXCL8) is a neutrophil chemotactic factor belonging to the family of chemokines. IL-8 was shown to resist pepsin cleavage displaying its high resistance to this protease. However, the molecular mechanisms underlying this resistance are not fully understood. Using our in-house database containing the data on three-dimensional arrangements of secondary structure elements from the whole Protein Data Bank, we found a striking structural similarity between IL-8 and pepsin inhibitor-3. Such similarity could play a key role in understanding IL-8 resistance to the protease pepsin. To support this hypothesis, we applied pepsin assays confirming that intact IL-8 is not degraded by pepsin in comparison to IL-8 in a denaturated state. Applying 1 H- 15 N Heteronuclear Single Quantum Coherence NMR measurements, we determined the putative regions at IL-8 that are potentially responsible for interactions with the pepsin. The results obtained in this work contribute to the understanding of the resistance of IL-8 to pepsin proteolysis in terms of its structural properties.

Description: This paper deals with the sampled-data stabilization problem for Takagi-Sugeno (T-S) fuzzy genetic regulatory networks with leakage delays. A novel Lyapunov-Krasovskii functional (LKF) is established by the non-uniform division of the delay intervals with triplex and quadruplex integral terms. Using such LKFs for constant and time-varying delay cases, new stability conditions are obtained in the T-S fuzzy framework. Based on this, a new condition for the sampled-data controller design is proposed using a linear matrix inequality representation. A numerical result is provided to show the effectiveness and potential of the developed design method.

Description: In existing works, the filters designed for delayed genetic regulatory networks (GRNs) contain time delay. If the time delay is unknown, the filters do not work in practical applications. In order to overcome the shortcoming in such existing works, this paper studies the filter design problem of GRNs with unknown constant time delay, and a novel adaptive filter is introduced, in which all unknown network parameters and the unknown time delay can be estimated online. By Lyapunove approach, it is shown that the estimating errors asymptotically converge to the origin. Finally, simulation results are presented to illustrate the effectiveness of the new method proposed in this paper.

Description: This article presents two new deterministic algorithms for constructing consensus trees. Given an input of $k$  phylogenetic trees with identical leaf label sets and $n$  leaves each, the first algorithm constructs the majority rule (+) consensus tree in $O(k n)$ time, which is optimal since the input size is $Omega (k n)$ , and the second one constructs the frequency difference consensus tree in $min lbrace O(k n^{2}), O(k n (k + log ^{2}n))rbrace$ time.

Description: Protein-protein interactions (PPIs) play a vital role in the biological processes involved in the cell functions and disease pathways. The experimental methods known to predict PPIs require tremendous efforts and the results are often hindered by the presence of a large number of false positives. Herein, we demonstrate the use of a new Genetic Programming (GP) based Symbolic Regression (SR) approach for predicting PPIs related to a disease. In this case study, a dataset consisting of 135 PPI complexes related to cancer was used to construct a generic PPI predicting model with good PPI prediction accuracy and generalization ability. A high correlation coefficient (CC) magnitude of 0.893, and low root mean square error (RMSE), and mean absolute percentage error (MAPE) values of 478.221 and 0.239, respectively, were achieved for both the training and test set outputs. To validate the discriminatory nature of the model, it was applied on a dataset of diabetes complexes where it yielded significantly low CC values. Thus, the GP model developed here serves a dual purpose: (a) a predictor of the binding energy of cancer related PPI complexes, and (b) a classifier for discriminating PPI complexes related to cancer from those of other diseases.

Description: Hajirasouliha and Raphael (WABI 2014) proposed a model for deconvoluting mixed tumor samples measured from a collection of high-throughput sequencing reads. This is related to understanding tumor evolution and critical cancer mutations. In short, their formulation asks to split each row of a binary matrix so that the resulting matrix corresponds to a perfect phylogeny and has the minimum number of rows among all matrices with this property. In this paper, we disprove several claims about this problem, including an NP-hardness proof of it. However, we show that the problem is indeed NP-hard, by providing a different proof. We also prove NP-completeness of a variant of this problem proposed in the same paper. On the positive side, we propose an efficient (though not necessarily optimal) heuristic algorithm based on coloring co-comparability graphs, and a polynomial time algorithm for solving the problem optimally on matrix instances in which no column is contained in both columns of a pair of conflicting columns. Implementations of these algorithms are freely available at https://github.com/alexandrutomescu/MixedPerfectPhylogeny .

Description: The research detailed in this paper focuses on the processing of Electroencephalography (EEG) data to identify attention during the learning process. The identification of affect using our procedures is integrated into a simulated distance learning system that provides feedback to the user with respect to attention and concentration. The authors propose a classification procedure that combines correlation-based feature selection (CFS) and a k-nearest-neighbor (KNN) data mining algorithm. To evaluate the CFS+KNN algorithm, it was test against CFS+C4.5 algorithm and other classification algorithms. The classification performance was measured 10 times with different 3-fold cross validation data. The data was derived from 10 subjects while they were attempting to learn material in a simulated distance learning environment. A self-assessment model of self-report was used with a single valence to evaluate attention on 3 levels (high, neutral, low). It was found that CFS+KNN had a much better performance, giving the highest correct classification rate (CCR) of $80.84 pm 3.0$ % for the valence dimension divided into three classes.

Description: The tandem duplication random loss operation (TDRL) is an important genome rearrangement operation in metazoan mitochondrial genomes. A TDRL consists of a duplication of a contiguous set of genes in tandem followed by a random loss of one copy of each duplicated gene. This paper presents an analysis of the combinatorics of TDRLs on circular genomes, e.g., the mitochondrial genome. In particular, results on TDRLs for circular genomes and their linear representatives are established. Moreover, the distance between gene orders with respect to linear TDRLs and circular TDRLs is studied. An analysis of the available animal mitochondrial gene orders shows the practical relevance of the theoretical results.

Description: Recent advances in high-throughput technologies have given rise to collecting large amounts of multidimensional heterogeneous data that provide diverse information on the same biological samples. Integrative analysis of such multisource datasets may reveal new biological insights into complex biological mechanisms and therefore remains an important research field in systems biology. Most of the modern integrative clustering approaches rely on independent analysis of each dataset and consensus clustering, probabilistic or statistical modeling, while flexible distance-based integrative clustering techniques are sparsely covered. We propose two distance-based integrative clustering frameworks based on bi-level and bi-objective extensions of the p-median problem. A hybrid branch-and-cut method is developed to find global optimal solutions to the bi-level p-median model. As to the bi-objective problem, an $varepsilon$ -constraint algorithm is proposed to generate an approximation to the Pareto optimal set. Every solution found by any of the frameworks corresponds to an integrative clustering. We present an application of our approaches to integrative analysis of NCI-60 human tumor cell lines characterized by gene expression and drug activity profiles. We demonstrate that the proposed mathematical optimization-based approaches outperform some state-of-the-art and traditional distance-based integrative and non-integrative clustering techniques.

Description: In this study, the expected time required to eradicate HIV-1 completely was found as the conditional absorbing time in a finite state space continuous-time Markov chain model. The Markov chain has two absorbing states: one corresponds to HIV eradication and another representing the possible disaster. This method allowed us to calculate the expected eradication time by solving systems of linear equations. To overcome the challenge of huge dimension of the problem, we applied a novel stop and resume technique. This technique also helped to stop the numerical computation whenever we wanted and continue later from that point until the final result was obtained. Our numerical study showed the dependence of the expected eradication time of HIV on the half-life of the latently infected cells and there agreed with the previous studies. The study predicted that when the half-life of the latent cells varied from 4.6 to 60 months, it took a mean 4.97 to 31.04 years with a corresponding standard deviation of 0.64 to 3.99 years to eradicate the latent cell reservoir. It also revealed the crucial dependence of eradication time on the initial number of latently infected cells.

Description: The identification of essential proteins in protein-protein interaction (PPI) networks is of great significance for understanding cellular processes. With the increasing availability of large-scale PPI data, numerous centrality measures based on network topology have been proposed to detect essential proteins from PPI networks. However, most of the current approaches focus mainly on the topological structure of PPI networks, and largely ignore the gene ontology annotation information. In this paper, we propose a novel centrality measure, called TEO, for identifying essential proteins by combining network topology, gene expression profiles, and GO information. To evaluate the performance of the TEO method, we compare it with five other methods (degree, betweenness, NC, Pec, and CowEWC) in detecting essential proteins from two different yeast PPI datasets. The simulation results show that adding GO information can effectively improve the predicted precision and that our method outperforms the others in predicting essential proteins.

Description: Network Alignment over graph-structured data has received considerable attention in many recent applications. Global network alignment tries to uniquely find the best mapping for a node in one network to only one node in another network. The mapping is performed according to some matching criteria that depend on the nature of data. In molecular biology, functional orthologs, protein complexes, and evolutionary conserved pathways are some examples of information uncovered by global network alignment. Current techniques for global network alignment suffer from several drawbacks, e.g., poor performance and high memory requirements. We address these problems by proposing IBNAL, Indexes-Based Network ALigner, for better alignment quality and faster results. To accelerate the alignment step, IBNAL makes use of a novel clique-based index and is able to align large networks in seconds. IBNAL produces a higher topological quality alignment and comparable biological match in alignment relative to other state-of-the-art aligners even though topological fit is primarily used to match nodes. IBNAL’s results confirm and give another evidence that homology information is more likely to be encoded in network topology than sequence information.

Description: Characterizing genes with semantic information is an important process regarding the description of gene products. In spite that complete genomes of many organisms have been already sequenced, the biological functions of all of their genes are still unknown. Since experimentally studying the functions of those genes, one by one, would be unfeasible, new computational methods for gene functions inference are needed. We present here a novel computational approach for inferring biological function for a set of genes with previously unknown function, given a set of genes with well-known information. This approach is based on the premise that genes with similar behaviour should be grouped together. This is known as the guilt-by-association principle. Thus, it is possible to take advantage of clustering techniques to obtain groups of unknown genes that are co-clustered with genes that have well-known semantic information (GO annotations). Meaningful knowledge to infer unknown semantic information can therefore be provided by these well-known genes. We provide a method to explore the potential function of new genes according to those currently annotated. The results obtained indicate that the proposed approach could be a useful and effective tool when used by biologists to guide the inference of biological functions for recently discovered genes. Our work sets an important landmark in the field of identifying unknown gene functions through clustering, using an external source of biological input. A simple web interface to this proposal can be found at http://fich.unl.edu.ar/sinc/webdemo/gamma-am/ .

Description: Entropy, being closely related to repetitiveness and compressibility, is a widely used information-related measure to assess the degree of predictability of a sequence. Entropic profiles are based on information theory principles, and can be used to study the under-/over-representation of subwords, by also providing information about the scale of conserved DNA regions. Here, we focus on the algorithmic aspects related to entropic profiles. In particular, we propose linear time algorithms for their computation that rely on suffix-based data structures, more specifically on the truncated suffix tree (TST) and on the enhanced suffix array (ESA). We performed an extensive experimental campaign showing that our algorithms, beside being faster, make it possible the analysis of longer sequences, even for high degrees of resolution, than state of the art algorithms.

Description: This study presents a machine learning method that increases the number of identified bases in Sanger Sequencing. The system post-processes a KB basecalled chromatogram. It selects a recoverable subset of N-labels in the KB-called chromatogram to replace with basecalls (A,C,G,T). An N-label correction is defined given an additional read of the same sequence, and a human finished sequence. Corrections are added to the dataset when an alignment determines the additional read and human agree on the identity of the N-label. KB must also rate the replacement with quality value of $>60$ in the additional read. Corrections are only available during system training. Developing the system, nearly 850,000 N-labels are obtained from Barcode of Life Datasystems, the premier database of genetic markers called DNA Barcodes. Increasing the number of correct bases improves reference sequence reliability, increases sequence identification accuracy, and assures analysis correctness. Keeping with barcoding standards, our system maintains an error rate of $〈1$ percent. Our system only applies corrections when it estimates low rate of error. Tested on this data, our automation selects and recovers: 79 percent of N-labels from COI (animal barcode); 80 percent from matK and rbcL (plant barcodes); and 58 percent from non-protein-coding sequences (across eukaryotes).

Description: In systems biology, network models are often used to study interactions among cellular components, a salient aim being to develop drugs and therapeutic mechanisms to change the dynamical behavior of the network to avoid undesirable phenotypes. Owing to limited knowledge, model uncertainty is commonplace and network dynamics can be updated in different ways, thereby giving multiple dynamic trajectories, that is, dynamics uncertainty. In this manuscript, we propose an experimental design method that can effectively reduce the dynamics uncertainty and improve performance in an interaction-based network. Both dynamics uncertainty and experimental error are quantified with respect to the modeling objective, herein, therapeutic intervention. The aim of experimental design is to select among a set of candidate experiments the experiment whose outcome, when applied to the network model, maximally reduces the dynamics uncertainty pertinent to the intervention objective.

Description: The $text{NJ}_{st}$ method was proposed by Liu and Yu to infer a species tree topology from unrooted topological gene trees. While its statistical consistency under the multispecies coalescent model was established only for a four-taxon tree, simulations demonstrated its good performance on gene trees inferred from sequences for many taxa. Here, we prove the statistical consistency of the method for an arbitrarily large species tree. Our approach connects $text{NJ}_{st}$ to a generalization of the STAR method of Liu, Pearl, and Edwards, and a previous theoretical analysis of it. We further show $text{NJ}_{st}$ utilizes only the distribution of splits in the gene trees, and not their individual topologies. Finally, we discuss how multiple samples per taxon per gene should be handled for statistical consistency.

Description: Computing similarity or dissimilarity between protein structures is an important task in structural biology. A conventional method to compute protein structure dissimilarity requires structural alignment of the proteins. However, defining one best alignment is difficult, especially when the structures are very different. In this paper, we propose a new similarity measure for protein structure comparisons using a set of multi-view 2D images of 3D protein structures. In this approach, each protein structure is represented by a subspace from the image set. The similarity between two protein structures is then characterized by the canonical angles between the two subspaces. The primary advantage of our method is that precise alignment is not needed. We employed Grassmann Discriminant Analysis (GDA) as the subspace-based learning in the classification framework. We applied our method for the classification problem of seven SCOP structural classes of protein 3D structures. The proposed method outperformed the k-nearest neighbor method (k-NN) based on conventional alignment-based methods CE, FATCAT, and TM-align. Our method was also applied to the classification of SCOP folds of membrane proteins, where the proposed method could recognize the fold HEM-binding four-helical bundle (f.21) much better than TM-Align.

Description: We describe a specialized methodology for segmenting 2D microscopy digital images of freshwater green microalgae. The goal is to obtain representative algae shapes to extract morphological features to be employed in a posterior step of taxonomical classification of the species. The proposed methodology relies on the seeded region growing principle and on a fine-tuned filtering preprocessing stage to smooth the input image. A contrast enhancement process then takes place to highlight algae regions on a binary pre-segmentation image. This binary image is also employed to determine where to place the seed points and to estimate the statistical probability distributions that characterize the target regions, i.e., the algae areas and the background, respectively. These preliminary stages produce the required information to set the homogeneity criterion for region growing. We evaluate the proposed methodology by comparing its resulting segmentations with a set of corresponding ground-truth segmentations (provided by an expert biologist) and also with segmentations obtained with existing strategies. The experimental results show that our solution achieves highly accurate segmentation rates with greater efficiency, as compared with the performance of standard segmentation approaches and with an alternative previous solution, based on level-sets, also specialized to handle this particular problem.