Dataset Information

Optimal sequence for chain matrix multiplication using evolutionary algorithm.

ABSTRACT: The Chain Matrix Multiplication Problem (CMMP) is an optimization problem that helps to find the optimal way of parenthesization for Chain Matrix Multiplication (CMM). This problem arises in various scientific applications such as in electronics, robotics, mathematical programing, and cryptography. For CMMP the researchers have proposed various techniques such as dynamic approach, arithmetic approach, and sequential multiplication. However, these techniques are deficient for providing optimal results for CMMP in terms of computational time and significant amount of scalar multiplication. In this article, we proposed a new model to minimize the Chain Matrix Multiplication (CMM) operations based on group counseling optimizer (GCO). Our experimental results and their analysis show that the proposed GCO model has achieved significant reduction of time with efficient speed when compared with sequential chain matrix multiplication approach. The proposed model provides good performance and reduces the multiplication operations varying from 45% to 96% when compared with sequential multiplication. Moreover, we evaluate our results with the best known dynamic programing and arithmetic multiplication approaches, which clearly demonstrate that proposed model outperforms in terms of computational time and space complexity.

SUBMITTER: Iqbal U

PROVIDER: S-EPMC7959611 | biostudies-literature | 2021

REPOSITORIES: biostudies-literature

ACCESS DATA

Publications

Optimal sequence for chain matrix multiplication using evolutionary algorithm.

Iqbal Umer U Shoukat Ijaz Ali IA Elahi Ihsan I Kanwal Afshan A Farrukh Bakhtawar B A Alqahtani Mohammed M Rauf Abdul A Alqurni Jehad Saad JS

PeerJ. Computer science 20210226

The Chain Matrix Multiplication Problem (CMMP) is an optimization problem that helps to find the optimal way of parenthesization for Chain Matrix Multiplication (CMM). This problem arises in various scientific applications such as in electronics, robotics, mathematical programing, and cryptography. For CMMP the researchers have proposed various techniques such as dynamic approach, arithmetic approach, and sequential multiplication. However, these techniques are deficient for providing optimal re ...[more]

PMID: 33817041

Similar Datasets

Project description:BackgroundSelective pressures at the DNA level shape genes into profiles consisting of patterns of rapidly evolving sites and sites withstanding change. These profiles remain detectable even when protein sequences become extensively diverged. A common task in molecular biology is to infer functional, structural or evolutionary relationships by querying a database using an algorithm. However, problems arise when sequence similarity is low. This study presents an algorithm that uses the evolutionary rate at codon sites, the dN/dS (ω) parameter, coupled to a substitution matrix as an alignment metric for detecting distantly related proteins. The algorithm, called BLOSUM-FIRE couples a newer and improved version of the original FIRE (Functional Inference using Rates of Evolution) algorithm with an amino acid substitution matrix in a dynamic scoring function. The enigmatic hepatitis B virus X protein was used as a test case for BLOSUM-FIRE and its associated database EvoDB.ResultsThe evolutionary rate based approach was coupled with a conventional BLOSUM substitution matrix. The two approaches are combined in a dynamic scoring function, which uses the selective pressure to score aligned residues. The dynamic scoring function is based on a coupled additive approach that scores aligned sites based on the level of conservation inferred from the ω values. Evaluation of the accuracy of this new implementation, BLOSUM-FIRE, using MAFFT alignment as reference alignments has shown that it is more accurate than its predecessor FIRE. Comparison of the alignment quality with widely used algorithms (MUSCLE, T-COFFEE, and CLUSTAL Omega) revealed that the BLOSUM-FIRE algorithm performs as well as conventional algorithms. Its main strength lies in that it provides greater potential for aligning divergent sequences and addresses the problem of low specificity inherent in the original FIRE algorithm. The utility of this algorithm is demonstrated using the Hepatitis B virus X (HBx) protein, a protein of unknown function, as a test case.ConclusionThis study describes the utility of an evolutionary rate based approach coupled to the BLOSUM62 amino acid substitution matrix in inferring protein domain function. We demonstrate that such an approach is robust and performs as well as an array of conventional algorithms.

Project description:Seizure prediction might be the solution to tackle the apparent unpredictability of seizures in patients with drug-resistant epilepsy, which comprise about a third of all patients with epilepsy. Designing seizure prediction models involves defining the pre-ictal period, a transition stage between inter-ictal brain activity and the seizure discharge. This period is typically a fixed interval, with some recent studies reporting the evaluation of different patient-specific pre-ictal intervals. Recently, researchers have aimed to determine the pre-ictal period, a transition stage between regular brain activity and a seizure. Authors have been using deep learning models given the ability of such models to automatically perform pre-processing, feature extraction, classification, and handling temporal and spatial dependencies. As these approaches create black-box models, clinicians may not have sufficient trust to use them in high-stake decisions. By considering these problems, we developed an evolutionary seizure prediction model that identifies the best set of features while automatically searching for the pre-ictal period and accounting for patient comfort. This methodology provides patient-specific interpretable insights, which might contribute to a better understanding of seizure generation processes and explain the algorithm's decisions. We tested our methodology on 238 seizures and 3687 h of continuous data, recorded on scalp recordings from 93 patients with several types of focal and generalised epilepsies. We compared the results with a seizure surrogate predictor and obtained a performance above chance for 32% patients. We also compared our results with a control method based on the standard machine learning pipeline (pre-processing, feature extraction, classifier training, and post-processing), where the control marginally outperformed our approach by validating 35% of the patients. In total, 54 patients performed above chance for at least one method: our methodology or the control one. Of these 54 patients, 21 ([Formula: see text]38%) were solely validated by our methodology, while 24 ([Formula: see text]44%) were only validated by the control method. These findings may evidence the need for different methodologies concerning different patients.

Project description:BackgroundWhile the pairwise alignments produced by sequence similarity searches are a powerful tool for identifying homologous proteins - proteins that share a common ancestor and a similar structure; pairwise sequence alignments often fail to represent accurately the structural alignments inferred from three-dimensional coordinates. Since sequence alignment algorithms produce optimal alignments, the best structural alignments must reflect suboptimal sequence alignment scores. Thus, we have examined a range of suboptimal sequence alignments and a range of scoring parameters to understand better which sequence alignments are likely to be more structurally accurate.ResultsWe compared near-optimal protein sequence alignments produced by the Zuker algorithm and a set of probabilistic alignments produced by the probA program with structural alignments produced by four different structure alignment algorithms. There is significant overlap between the solution spaces of structural alignments and both the near-optimal sequence alignments produced by commonly used scoring parameters for sequences that share significant sequence similarity (E-values < 10-5) and the ensemble of probA alignments. We constructed a logistic regression model incorporating three input variables derived from sets of near-optimal alignments: robustness, edge frequency, and maximum bits-per-position. A ROC analysis shows that this model more accurately classifies amino acid pairs (edges in the alignment path graph) according to the likelihood of appearance in structural alignments than the robustness score alone. We investigated various trimming protocols for removing incorrect edges from the optimal sequence alignment; the most effective protocol is to remove matches from the semi-global optimal alignment that are outside the boundaries of the local alignment, although trimming according to the model-generated probabilities achieves a similar level of improvement. The model can also be used to generate novel alignments by using the probabilities in lieu of a scoring matrix. These alignments are typically better than the optimal sequence alignment, and include novel correct structural edges. We find that the probA alignments sample a larger variety of alignments than the Zuker set, which more frequently results in alignments that are closer to the structural alignments, but that using the probA alignments as input to the regression model does not increase performance.ConclusionsThe pool of suboptimal pairwise protein sequence alignments substantially overlaps structure-based alignments for pairs with statistically significant similarity, and a regression model based on information contained in this alignment pool improves the accuracy of pairwise alignments with respect to structure-based alignments.

Dataset Information

Optimal sequence for chain matrix multiplication using evolutionary algorithm.

Publications

Optimal sequence for chain matrix multiplication using evolutionary algorithm.

Similar Datasets

OmicsDI is part of the ELIXIR infrastructure

Tweets