Search

Background: Identifying genes that instigate cell anomalies and cause cancer in humans is an important field in oncology research. Abnormalities in these genes are transferred to other genes in the cell, disrupting its normal functionality. Such genes are known as cancer driver genes (CDGs). Various methods have been proposed for predicting CDGs, mostly based on genomic data and computational methods. Some novel bioinformatic approaches have been developed. Objective: In this article, we propose a network-based algorithm, SalsaDriver (Stochastic approach for link-structure analysis for driver detection), which can calculate each gene's receiving and influencing power using the stochastic analysis of regulatory interaction structures in gene regulatory networks. Method: First, regulatory networks related to breast, colon, and lung cancers are constructed using gene expression data and a list of regulatory interactions, the weights of which are then calculated using biological and topological features of the network. After that, the weighted regulatory interactions are used in the structural analysis of interactions, with two separate Markov chains on the bipartite graph taken from the main graph of the gene network and the implementation of the stochastic approach for link-structure analysis. The proposed algorithm categorizes higher-ranked genes as driver genes. Results: The proposed algorithm was compared with 24 other computational and network tools based on the F-measure value and the number of detected CDGs. The results were validated using four databases. The findings of this study show that SalsaDriver outperforms other methods and can identify substantiallyy more driver genes than other methods. Conclusion: The SalsaDriver network-based approach is suitable for predicting CDGs and can be used as a complementary method along with other computational tools.

Controllability of a complex network system is related to finding a set of minimum number of nodes, known as drivers, controlling which allows having a full control on the dynamics of the network. For some applications, only a portion of the network is required to be controlled, for which target control has been proposed. Often, along the controlling route from driver nodes to target nodes, some mediators (intermediate nodes) are also unwillingly controlled, which might cause various side effects. In controlling cancerous cells, unwillingly controlling healthy cells, might result in weakening them, thus affecting the immune system against cancer. This manuscript proposes a suitable candidate solution to the problem of finding minimum number of driver nodes under minimal mediators. Although many others have attempted to develop algorithms to find minimum number of drivers for target control, the newly proposed algorithm is the first one that is capable of achieving this goal and at the same time, keeping the number of the mediators to a minimum. The proposed controllability condition, based on path lengths between node pairs, meets Kalman's controllability rank condition and can be applied on directed networks. Our results show that the path length is a major determinant of in properties of the target control under minimal mediators. As the average path length becomes larger, the ratio of drivers to target nodes decreases and the ratio of mediators to targets increases. The proposed methodology has potential applications in biological networks. The source code of the algorithm and the networks that have been used are available from the following link: https://github.com/LBBSoft/Target-Control-with-Minimal-Mediators.git

Complexity of cascading interrelations between molecular cell components at different levels from genome to metabolome ordains a massive difficulty in comprehending biological happenings. However, considering these complications in the systematic modelings will result in realistic and reliable outputs. The multilayer networks approach is a relatively innovative concept that could be applied for multiple omics datasets as an integrative methodology to overcome heterogeneity difficulties. Herein, we employed the multilayer framework to rehabilitate colon adenocarcinoma network by observing co-expression correlations, regulatory relations, and physical binding interactions. Hub nodes in this three-layer network were selected using a heterogeneous random walk with random jump procedure. We exploited local composite modules around the hub nodes having high overlay with cancer-specific pathways, and investigated their genes showing a different expressional pattern in the tumor progression. These genes were examined for survival effects on the patient’s lifespan, and those with significant impacts were selected as potential candidate biomarkers. Results suggest that identified genes indicate noteworthy importance in the carcinogenesis of the colon.

Protein sequences can be viewed as a language; therefore, we benefit from using the models initially developed for natural languages such as transformers. ProtAlbert is one of the best pre-trained transformers on protein sequences, and its efficiency enables us to run the model on longer sequences with less computation power while having similar performance with the other pre-trained transformers. This paper includes two main parts: transformer analysis and profile prediction. In the first part, we propose five algorithms to assess the attention heads in different layers of ProtAlbert for five protein characteristics, nearest-neighbor interactions, type of amino acids, biochemical and biophysical properties of amino acids, protein secondary structure, and protein tertiary structure. These algorithms are performed on 55 proteins extracted from CASP13 and three case study proteins whose sequences, experimental tertiary structures, and HSSP profiles are available. This assessment shows that although the model is only pre-trained on protein sequences, attention heads in the layers of ProtAlbert are representative of some protein family characteristics. This conclusion leads to the second part of our work. We propose an algorithm called PA_SPP for protein sequence profile prediction by pre-trained ProtAlbert using masked-language modeling. PA_SPP algorithm can help the researchers to predict an HSSP profile while there are no similar sequences to a query sequence in the database for making the HSSP profile.

In this paper, we present a new generation algorithm with corresponding ranking and unranking algorithms for (k, m)-ary trees in B-order. (k, m)-ary tree is introduced by Du and Liu. A (k, m)-ary tree is a generalization of k-ary tree, whose every node of even level of the tree has degree k and odd level of the tree has degree 0 or m. Up to our knowledge no generation, ranking or unranking algorithms are given in the literature for this family of trees. We use Zaks’ encoding for representing (k, m)-ary trees and to generate them in B-order. We also prove that, to generate (k, m)-ary trees in B-order using this encoding, the corresponding codewords should be generated in reverse-lexicographical ordering. The presented generation algorithm has a constant average time and O(n) time complexity in the worst case. Due to the given encoding, both ranking and unranking algorithms are also presented taking O(n) and $$O(n\log n)$$ time complexity, respectively.

Biological networks have recently gathered much attraction in finding their motifs. Motifs can be considered as subgraphs that occur in a particular network at significantly higher frequencies than random networks. The importance of this problem causes attention of improving the existing algorithms. As the runtime of an algorithm is an important aspect, applying parallel techniques is appropriate for better improvement. In this paper a parallel algorithm (ParaKavosh) for finding network motifs is presented. Our algorithm is tested on E. coli, S. cerevisiae, Homo sapiens and Rattus norvegicus networks. The cost optimality of the algorithm is also shown by analyzing the obtained results with an efficient sequential algorithm. The results show that the algorithm performs much better in terms of runtime.

Controlling a network structure has many potential applications many fields. In order to have an effective network control, not only finding good driver nodes is important, but also finding the optimal time to apply the external control signals to network nodes has a critical role. If applied in an appropriate time, one might be to control a network with a smaller control signals, and thus less energy. In this manuscript, we show that there is a relationship between the strength of the internal fluxes and the effectiveness of the external control signal. To be more effective, external control signals should be applied when the strength of the internal states is the smallest. We validate this claim on synthetic networks as well as a number of real networks. Our results may have important implications in systems medicine, in order to find the most appropriate time to inject drugs as a signal to control diseases.

Regardless of all efforts on community discovery algorithms, it is still an open and challenging subject in network science. Recognizing communities in a multilayer network, where there are several layers (types) of connections, is even more complicated. Here, we concentrated on a specific type of communities called seed-centric local communities in the multilayer environment and developed a novel method based on the information cascade concept, called PLCDM. Our simulations on three datasets (real and artificial) signify that the suggested method outstrips two known earlier seed-centric local methods. Additionally, we compared it with other global multilayer and single-layer methods. Eventually, we applied our method on a biological two-layer network of Colon Adenocarcinoma (COAD), reconstructed from transcriptomic and post-transcriptomic datasets, and assessed the output modules. The functional enrichment consequences infer that the modules of interest hold biomolecules involved in the pathways associated with the carcinogenesis.

Stem cells, with their capacity to self-renew and to differentiate to more specialized cell types, play a key role to maintain homeostasis in adult tissues. To investigate how, in the dynamic stochastic environment of a tissue, non-genetic diversity and the precise balance between proliferation and differentiation are achieved, it is necessary to understand the molecular mechanisms of the stem cells in decision making process. By focusing on the impact of stochasticity, we proposed a computational model describing the regulatory circuitry as a tri-stable dynamical system to reveal the mechanism which orchestrate this balance. Our model explains how the distribution of noise in genes, linked to the cell regulatory networks, controls cell decision-making to maintain homeostatic state. The noise control over tissue homeostasis is achieved by regulating the probability of differentiation and self-renewal through symmetric and/or asymmetric cell divisions. Our model reveals, when mutations due to the replication of DNA in stem cell division, are inevitable, how mutations contribute to either aging gradually or the development of cancer in a short period of time. Furthermore, our model sheds some light on the impact of more complex regulatory networks on the system robustness against perturbations.

RNA secondary structures are important in many biological processes since there is a close relationship between structure and function in biology. There is a known bijection between the possible shapes of a single-stranded RNA molecule of fixed length and trees with n nodes and m leaves, $$\mathcal {T}(n, m)$$ . In this article, we present a sequential algorithm for generating such trees in A-order. The worst case time complexity of the presented algorithm is O(n). We also develop a parallel version of the algorithm which is both cost-optimal and adaptive. We use Exclusive Read Exclusive Write Shared Memory Single Instruction Multiple Data multi-processor architecture. Moreover, the generated trees are in A-order.

Background Acute lymphoblastic leukemia (ALL) is the most common type of cancer diagnosed in children and Glucocorticoids (GCs) form an essential component of the standard chemotherapy in most treatment regimens. The category of infant ALL patients carrying a translocation involving the mixed lineage leukemia (MLL) gene (gene KMT2A) is characterized by resistance to GCs and poor clinical outcome. Although some studies examined GC-resistance in infant ALL patients, the understanding of this phenomenon remains limited and impede the efforts to improve prognosis. Methods This study integrates differential co-expression (DC) and protein-protein interaction (PPI) networks to find active protein modules associated with GC-resistance in MLL-rearranged infant ALL patients. A network was constructed by linking differentially co-expressed gene pairs between GC-resistance and GC-sensitive samples and later integrated with PPI networks by keeping the links that are also present in the PPI network. The resulting network was decomposed into two sub-networks, specific to each phenotype. Finally, both sub-networks were clustered into modules using weighted gene co-expression network analysis (WGCNA) and further analyzed with functional enrichment analysis. Results Through the integration of DC analysis and PPI network, four protein modules were found active under the GC-resistance phenotype but not under the GC-sensitive. Functional enrichment analysis revealed that these modules are related to proteasome, electron transport chain, tRNA-aminoacyl biosynthesis, and peroxisome signaling pathways. These findings are in accordance with previous findings related to GC-resistance in other hematological malignancies such as pediatric ALL. Conclusions Differential co-expression analysis is a promising approach to incorporate the dynamic context of gene expression profiles into the well-documented protein interaction networks. The approach allows the detection of relevant protein modules that are highly enriched with DC gene pairs. Functional enrichment analysis of detected protein modules generates new biological hypotheses and may help in explaining the GC-resistance in MLL-rearranged infant ALL patients. Electronic supplementary material The online version of this article (10.1186/s10020-019-0106-1) contains supplementary material, which is available to authorized users.

International audience; Application of deep convolutional spiking neural networks (SNNs) to artificial intelligence (AI) tasks has recently gained a lot of interest since SNNs are hardware-friendly and energy-efficient. Unlike the non-spiking counterparts, most of the existing SNN simulation frameworks are not practically efficient enough for large-scale AI tasks. In this paper, we introduce SpykeTorch, an open-source high-speed simulation framework based on PyTorch. This framework simulates convolutional SNNs with at most one spike per neuron and the rank-order encoding scheme. In terms of learning rules, both spike-timing-dependent plasticity (STDP) and reward-modulated STDP (R-STDP) are implemented, but other rules could be implemented easily. Apart from the aforementioned properties, SpykeTorch is highly generic and capable of reproducing the results of various studies. Computations in the proposed framework are tensor-based and totally done by PyTorch functions, which in turn brings the ability of just-in-time optimization for running on CPUs, GPUs, or Multi-GPU platforms.

Despite vast improvements that have been made in the treatment of children with acute lymphoblastic leukemia (ALL), the majority of infant ALL patients (~80 %, < 1 year of age) that carry a chromosomal translocation involving the mixed lineage leukemia (MLL) gene shows a poor response to chemotherapeutic drugs, especially glucocorticoids (GCs), which are essential components of all current treatment regimens. Although addressed in several studies, the mechanism(s) underlying this phenomenon have remained largely unknown. A major drawback of most previous studies is their primary focus on individual genes, thereby neglecting the putative significance of inter-gene correlations. Here, we aimed at studying GC resistance in MLL-rearranged infant ALL patients by inferring an associated module of genes using co-expression network analysis. The implications of newly identified candidate genes with associations to other well-known relevant genes from the same module, or with associations to known transcription factor or microRNA interactions, were substantiated using literature data. A weighted gene co-expression network was constructed to identify gene modules associated with GC resistance in MLL-rearranged infant ALL patients. Significant gene ontology (GO) terms and signaling pathways enriched in relevant modules were used to provide guidance towards which module(s) consisted of promising candidates suitable for further analysis. Through gene co-expression network analysis a novel set of genes (module) related to GC-resistance was identified. The presence in this module of the S100 and ANXA genes, both well-known biomarkers for GC resistance in MLL-rearranged infant ALL, supports its validity. Subsequent gene set net correlation analyses of the novel module provided further support for its validity by showing that the S100 and ANXA genes act as ‘hub’ genes with potentially major regulatory roles in GC sensitivity, but having lost this role in the GC resistant phenotype. The detected module implicates new genes as being candidates for further analysis through associations with known GC resistance-related genes. From our data we conclude that available systems biology approaches can be employed to detect new candidate genes that may provide further insights into drug resistance of MLL-rearranged infant ALL cases. Such approaches complement conventional gene-wise approaches by taking putative functional interactions between genes into account.

Parrondo’s paradox appears in game theory which asserts that playing two losing games, A and B (say) randomly or periodically may result in a winning expectation. In the original paradox the strategy of game B was capital-dependent. Some extended versions of the original Parrondo’s game as history dependent game, cooperative Parrondo’s game and others have been introduced. In all of these methods, games are played by two players. In this paper, we introduce a generalized version of this paradox by considering three players. In our extension, two games are played among three players by throwing a three-sided dice. Each player will be in one of three places in the game. We set up the conditions for parameters under which player 1 is in the third place in two games A and B. Then paradoxical property is obtained by combining these two games periodically and chaotically and (s)he will be in the first place when (s)he plays the games in one of the mentioned fashions. Mathematical analysis of the generalized strategy is presented and the results are also justified by computer simulations. A potential application of the model in treatment of type II diabetes is presented. In this theoretical work, we consider two types of treatments as two games which are played among three different players. The player 1 is considered as the treatment success index, the player 2 is the insulin deficiency index and the player 3 is assumed to be the insulin resistance index. It is shown that certain combinations of two losing games for player 1 (unsuccessful treatments) will result in a win (successful treatment).

The human visual system contains a hierarchical sequence of modules that take part in visual perception at superordinate, basic, and subordinate categorisation levels. The top-down signals facilita...

Reinforcement learning (RL) has recently regained popularity, with major achievements such as beating the European game of Go champion. Here, for the first time, we show that RL can be used efficiently to train a spiking neural network (SNN) to perform object recognition in natural images without using an external classifier. We used a feedforward convolutional SNN and a temporal coding scheme where the most strongly activated neurons fire first, while less activated ones fire later, or not at all. In the highest layers, each neuron was assigned to an object category, and it was assumed that the stimulus category was the category of the first neuron to fire. If this assumption was correct, the neuron was rewarded, i.e. spike-timing-dependent plasticity (STDP) was applied, which reinforced the neuron's selectivity. Otherwise, anti-STDP was applied, which encouraged the neuron to learn something else. As demonstrated on various image datasets (Caltech, ETH-80, and NORB), this reward modulated STDP (R-STDP) approach extracted particularly discriminative visual features, whereas classic unsupervised STDP extracts any feature that consistently repeats. As a result, R-STDP outperformed STDP on these datasets. Furthermore, R-STDP is suitable for online learning, and can adapt to drastic changes such as label permutations. Finally, it is worth mentioning that both feature extraction and classification were done with spikes, using at most one spike per neuron. Thus the network is hardware friendly and energy efficient., Comment: supplementary materials are added, Caltech face/motorbike demonstration figure is updated, some parts of the main manuscript are moved to the supplementary materials, additional network analysis and performance comparison with deep nets are added

The primate visual system has inspired the development of deep artificial neural networks, which have revolutionized the computer vision domain. Yet these networks are much less energy-efficient than their biological counterparts, and they are typically trained with backpropagation, which is extremely data-hungry. To address these limitations, we used a deep convolutional spiking neural network (DCSNN) and a latency-coding scheme. We trained it using a combination of spike-timing-dependent plasticity (STDP) for the lower layers and reward-modulated STDP (R-STDP) for the higher ones. In short, with R-STDP a correct (resp. incorrect) decision leads to STDP (resp. anti-STDP). This approach led to an accuracy of $97.2\%$ on MNIST, without requiring an external classifier. In addition, we demonstrated that R-STDP extracts features that are diagnostic for the task at hand, and discards the other ones, whereas STDP extracts any feature that repeats. Finally, our approach is biologically plausible, hardware friendly, and energy-efficient., Pattern Recognition (2019)

Background Discriminating driver mutations from the ones that play no role in cancer is a severe bottleneck in elucidating molecular mechanisms underlying cancer development. Since protein domains are representatives of functional regions within proteins, mutations on them may disturb the protein functionality. Therefore, studying mutations at domain level may point researchers to more accurate assessment of the functional impact of the mutations. Results This article presents a comprehensive study to map mutations from 29 cancer types to both sequence- and structure-based domains. Statistical analysis was performed to identify candidate domains in which mutations occur with high statistical significance. For each cancer type, the corresponding type-specific domains were distinguished among all candidate domains. Subsequently, cancer type-specific domains facilitated the identification of specific proteins for each cancer type. Besides, performing interactome analysis on specific proteins of each cancer type showed high levels of interconnectivity among them, which implies their functional relationship. To evaluate the role of mitochondrial genes, stem cell-specific genes and DNA repair genes in cancer development, their mutation frequency was determined via further analysis. Conclusions This study has provided researchers with a publicly available data repository for studying both CATH and Pfam domain regions on protein-coding genes. Moreover, the associations between different groups of genes/domains and various cancer types have been clarified. The work is available at http://www.cancerouspdomains.ir. Electronic supplementary material The online version of this article (doi:10.1186/s12859-017-1779-5) contains supplementary material, which is available to authorized users.

Background Although different protein-protein physical interaction (PPI) datasets exist for Escherichia coli, no common methodology exists to integrate these datasets and extract reliable modules reflecting the existing biological process and protein complexes. Naïve Bayesian formula is the highly accepted method to integrate different PPI datasets into a single weighted PPI network, but detecting proper weights in such network is still a major problem. Results In this paper, we proposed a new methodology to integrate various physical PPI datasets into a single weighted PPI network in a way that the detected modules in PPI network exhibit the highest similarity to available functional modules. We used the co-expression modules as functional modules, and we shown that direct functional modules detected from Gene Ontology terms could be used as an alternative dataset. After running this integrating methodology over six different physical PPI datasets, orthologous high-confidence interactions from a related organism and two AP-MS PPI datasets gained high weights in the integrated networks, while the weights for one AP-MS PPI dataset and two other datasets derived from public databases have converged to zero. The majority of detected modules shaped around one or few hub protein(s). Still, a large number of highly interacting protein modules were detected which are functionally relevant and are likely to construct protein complexes. Conclusions We provided a new high confidence protein complex prediction method supported by functional studies and literature mining. Electronic supplementary material The online version of this article (doi:10.1186/s12859-016-1422-x) contains supplementary material, which is available to authorized users.

Mixture of Experts is one of the most popular ensemble methods in pattern recognition systems. Although, diversity between the experts is one of the necessary conditions for the success of combining methods, ensemble systems based on Mixture of Experts suffer from the lack of enough diversity among the experts caused by unfavorable initial parameters. In the conventional Mixture of Experts, each expert receives the whole feature space. To increase diversity among the experts, solve the structural issues of Mixture of Experts such as zero coefficient problem, and improve efficiency in the system, we intend to propose a model, entitled Mixture of Feature Specified Experts, in which each expert gets a different subset of the original feature set. To this end, we first select a set of feature subsets which lead to a set of diverse and efficient classifiers. Then the initial parameters are infused to the system with training classifiers on the selected feature subsets. Finally, we train the expert and the gating networks using the learning rule of classical Mixture of Experts to organize collaboration between the members of system and aiding the gating network to find the best partitioning of the problem space. To evaluate our proposed method, we have used six datasets from the UCI repository. In addition the generalization capability of our proposed method is considered on real-world database of EEG based Brain-Computer Interface. The performance of our method is evaluated with various appraisal criteria and significant improvement in recognition rate of our proposed method is indicated in all practical tests.

Background: RNA plays key role in many aspects of biological processes and its tertiary structure is critical for its biological function. RNA secondary structure represents various significant portions of RNA tertiary structure. Since the biological function of RNA is concluded indirectly from its primary structure, it would be important to analyze the relations between the RNA sequences and their structures. One important tool to perform this kind of analysis is the neutral network which is a collection of RNA sequences, all coding the same secondary structure, where each RNA sequence is distinguished from the others by no more than a single base mutation. Another high level and useful representation of an RNA secondary structure is the RNA shape, where it is holding the vicinity and nesting of structural components and reducing their lengths to one unit. This allows us to analyze the huge structural space corresponding to the larger RNA sequences. Objectives: In this study, a new concept, entitled Variation Network, over the set of all RNA shapes is introduced. Based on this concept, the potential relations between random and natural RNA sequences, as well as their corresponding structures are analyzed. Materials and Methods: To explore the relations between random and natural RNA sequences and their corresponding structures, different properties including frequency, normalized frequency, shape energy average, variation rate, normalized variation rate, neighborhood energy average, and stability were obtained and analyzed. Results: The correlations among these properties of random and natural Variation Networks are presented. Base on the obtained correlations, all the employed datasets are highly correlated to each other from the frequency point of view, whereas they are not well correlated from the thermodynamic energy point of view. Conclusions: Since the thermodynamic energy value of an RNA sequence over its secondary structure plays a key role in its function, this research conclude that the natural RNA sequences are not generated randomly.

Background: RNA molecules play many important regulatory, catalytic and structural roles in the cell, and RNA secondary structure prediction with pseudoknots is one the most important problems in biology. An RNA pseudoknot is an element of the RNA sec ondary structure in which bases of a single-stranded loop pair with complementary bases outside the loop. Modeling these nested structures (pseudoknots) causes numerous com putational diffilties and so it has been generally neglected in RNA structure prediction algorithms. Objectives: In this study, we present a new heuristic algorithm for the Prediction of RNA Knotted structures using Tree Adjoining Grammars (named PreRKTAG). Materials and Methods: For a given RNA sequence, PreRKTAG uses a genetic algorithm on tree adjoining grammars to propose a structure with minimum thermodynamic energy. The genetic algorithm employs a subclass of tree adjoining grammars as individuals by which the secondary structure of RNAs are modeled. Upon the tree adjoining grammars, new crossover and mutation operations were designed.The finess function is defied ac cording to the RNA thermodynamic energy function, which causes the algorithm conver gence to be a stable structure. Results: The applicability of our algorithm is demonstrated by comparing its iresults with three well-known RNA secondary structure prediction algorithms that support crossed structures. Conclusions: We performed our comparison on a set of RNA sequences from the RNAseP database, where the outcomes show effiency and practicality of the proposed algorithm.

Gene expression is the main cause for the existence of various phenotypes. Through this procedure, the information stored in DNA rises to the phenotype. Essentially, gene expression is dependent upon the successful binding of transcription factors (TFs) - a specific type of proteins - to explicit positions in its upstream, TF binding sites (TFBSs). Unfortunately, finding these TFBSs is costly and laborious; therefore, discovering TFBSs computationally is a significant problem that many researches endeavor to solve. In this paper, a new TFBS discovery method is presented by considering known biological facts about TFBSs. The input to this method includes sequences with arbitrary lengths and the output comprises positions that tend to be TFBS. Through the application of previous methods along with a method that focuses on biological and simulated datasets, it is shown that this method achieves higher accuracy in discovering TFBSs.

The strongly NP-Hard Double Digest Problem, for reconstructing the physical map of DNA sequence, in now using for efficient genotyping. Most of the existing methods are inefficient in tackling large instances due to the large search space for the problem which grows as a factorial function (a!)(b!) of the numbers a and b of the DNA fragments generated by the two restriction enzymes. Also, none of the existing methods are able to handle the erroneous data. In this paper, we develop a novel method based on genetic algorithm for solving this problem and it is adapted to handle the erroneous data. Our genetic algorithm is implemented and compared with the other well-known existing algorithms. The obtained results show the efficiency (speedup) of our algorithm with respect to the other methods, specially for erroneous data.

Protein structural class prediction is one of the challenging problems in bioinformatics. Previous methods directly based on the similarity of amino acid (AA) sequences have been shown to be insufficient for low-similarity protein data-sets. To improve the prediction accuracy for such low-similarity proteins, different methods have been recently proposed that explore the novel feature sets based on predicted secondary structure propensities. In this paper, we focus on protein structural class prediction using combinations of the novel features including secondary structure propensities as well as functional domain (FD) features extracted from the InterPro signature database. Our comprehensive experimental results based on several benchmark data-sets have shown that the integration of new FD features substantially improves the accuracy of structural class prediction for low-similarity proteins as they capture meaningful relationships among AA residues that are far away in protein sequence. The proposed prediction method has also been tested to predict structural classes for partially disordered proteins with the reasonable prediction accuracy, which is a more difficult problem comparing to structural class prediction for commonly used benchmark data-sets and has never been done before to the best of our knowledge. In addition, to avoid overfitting with a large number of features, feature selection is applied to select discriminating features that contribute to achieve high prediction accuracy. The selected features have been shown to achieve stable prediction performance across different benchmark data-sets.

In this paper, a new efficient algorithm is presented for haplotype block partitioning based on haplotype diversity. In this algorithm, finding the largest meaningful block that satisfies the diversity condition is the main goal as an optimization problem. The algorithm can be performed in polynomial time complexity with regard to the number of haplotypes and SNPs. We apply our algorithm on three biological data sets from chromosome 21 in three different population data sets from HapMap data bulk; the obtained results show the efficiency and better performance of our algorithm in comparison with three other well known methods.

Single Nucleotide Polymorphisms (SNPs) provide valuable information on human evolutionary history and may lead us to identify genetic variants responsible for human complex diseases. Unfortunately, molecular haplotyping methods are costly, laborious, and time consuming; therefore, algorithms for constructing full haplotype patterns from small available data through computational methods, Tag SNP selection problem, are convenient and attractive. This problem is proved to be an NP-hard problem, so heuristic methods may be useful. In this paper we present a heuristic method based on genetic algorithm to find reasonable solution within acceptable time. The algorithm was tested on a variety of simulated and experimental data. In comparison with the exact algorithm, based on brute force approach, results show that our method can obtain optimal solutions in almost all cases and runs much faster than exact algorithm when the number of SNP sites is large. Our software is available upon request to the corresponding author.

The structure of RNA is often the key to its function and there is a close relationship between structure and function in biology. In this paper, we present a new algorithm for generating the possible shapes of a single-stranded RNA molecule of length l. We use a bijection between the secondary structure and specific ordered trees. Hence, generating different types of RNA becomes equivalent to the generation of these trees. The generated trees are encoded as integer sequences and are produced in A-order. The time complexity of the presented algorithm is O(l-k) where l is the number of bases and k, the number of pairings. Ranking and unranking algorithms with O(kl-k2) and O(l2+k2) time complexity are also presented.

We present a new molecular algorithm for adding two binary numbers with n bits. Without considering the generation of input, this algorithm can be performed in O(1) in a test tube using O(n) different types of DNA strands, and the output can be detected in O ( n ). The output strands, prior to read out operation, can serve as the input strands for another round of addition. The algorithm can be easily extended to any other logical operation, and even for adding two decimal numbers.

In this paper a novel genetic algorithm is presented for the dyad motif finding problem. The genetic algorithm uses a multi-objective fitness function based on the sum of pairs, the number of matches, and the information content. The individuals required for the population pool in the genetic algorithm are optimized by Gibbs sampling method. Also, new crossover and mutation operators are designed. The algorithm is implemented and tested on the different types of real datasets. The results are compared with other well-known algorithms and the effectiveness of our algorithm is shown.

We present a cost-optimal and adaptive parallel algorithm for generating t-ary trees in A-order. The generation is based on an encoding using integer sequences (z-sequences) due to Zaks [(1980), Lexicographic generation of ordered tree. Theor. Comput. Sci., 10, 63–82]. Our algorithm is the first introduced parallel generation algorithm, which generates t-ary trees in A-order in the literature. The used computational model is CREW SM SIMD multi-processors. This algorithm is designed based on a novel sequential generation algorithm that is also discussed. Ranking and unranking algorithms for z-sequences are also presented.

A neuronal tree is a rooted tree with n leaves whose each internal node has at least two children; this class not only is defined based on the structure of dendrites in neurons, but also refers to phylogenetic trees or evolutionary trees. More precisely, neuronal trees are rooted-multistate phylogenetic trees whose size is defined as the number of leaves. In this paper, a new encoding over an alphabet of size 3 (minimal cardinality) is introduced for representing the neuronal trees with a given number of leaves. This encoding is used for generating neuronal trees with n leaves in A-order with constant average time and O(n) time complexity in the worst case. Also, new ranking and unranking algorithms are presented in time complexity of O(n) and O(n log n), respectively.

In this paper, we present a new DNA-based evaluation algorithm for a Boolean circuit that employs standard bio-molecular techniques. The algorithm operates on an unbounded fan-in Boolean circuit consisting of AND and OR gates. The whole simulation of our algorithm is proposed in a single test tube in O(1) time complexity and is much easier to implement in the laboratory than previously described models. Furthermore, the algorithm allows for evaluating any number of Boolean circuits in parallel in a single test tube.

We present a new parallel algorithm for generating binary trees; it generates trees in A-order using A-sequences representation. This algorithm is adaptive and cost-optimal and is executed on a shared memory multiprocessor. We know of no other parallel algorithm in the literature that generates trees in A-order. This parallel algorithm is designed based on a presented sequential generation algorithm for A-sequences, with O(1) average time complexity.

We define Ballot-sequences for t-ary trees based on the ideas of Ballot-sequences of binary trees presented by Rotem. Later an efficient algorithm for the generation of t-ary trees with Ballot-sequences in B-order is presented. The algorithm generates each sequence in constant average time O(1), and the sequences are generated in lexicographical order. The ranking and unranking algorithms with O(tn) time complexity are also described.

Two parallel algorithms are presented for solving the minimum cost spanning tree problem in any undirected graph. These algorithms are parallel formulations of DHEA algorithm using Depth-First Search of the graph. The cost-optimality of both algorithms are investigated.

To date, few tools for aligning protein-protein interaction networks have been suggested. These tools typically find conserved interaction patterns using various local or global alignment algorithms. However, the improvement of the speed, scalability, simplification, and accuracy of network alignment tools is still the target of new researches. In this paper, we introducePin-Align, a new tool for local alignment of protein-protein interaction networks.Pin-Alignaccuracy is tested on protein interaction networks from IntAct, DIP, and the Stanford Network Database and the results are compared with other well-known algorithms. It is shown thatPin-Alignhas higher sensitivity and specificity in terms of KEGG Ortholog groups.