Prediction of Intrinsically Disordered Proteins with a Low Computational Complexity Method

The prediction of intrinsically disordered proteins is a hot research area in bio-information.Due to the high cost of experimental methods to evaluate disordered regions of protein sequences,it is becoming increasingly important to predict those regions through computational methods.In this paper,we developed a novel scheme by employing sequence complexity to calculate six features for each residue of a protein sequence,which includes the Shannon entropy,the topological entropy,the sample entropy and three amino acid preferences including Remark 465,Deleage/Roux,and Bfactor(2STD).Particularly,we introduced the sample entropy for calculating time series complexity by mapping the amino acid sequence to a time series of 0-9.To our knowledge,the sample entropy has not been previously used for predicting IDPs and hence is being used for the first time in our study.In addition,the scheme used a properly sized sliding window in every protein sequence which greatly improved the prediction performance.Finally,we used seven machine learning algorithms and tested with 10-fold cross-validation to get the results on the dataset R80 collected by Yang et al.and of the dataset DIS1556 from the Database of Protein Disorder(DisProt)(https://www.disprot.org)containing experimentally determined intrinsically disordered proteins(IDPs).The results showed that k-Nearest Neighbor was more appropriate and an overall prediction accuracy of 92%.Furthermore,our method just used six features and hence required lower computational complexity.

Computational complexity of spin-glass three-dimensional(3D)Ising model

In this work,the computational complexity of a spin-glass three-dimensional(3D)Ising model(for the lattice sizeN=lmn,wherel,m,n are thenumbersof lattice points along three crystallographic directions)is studied.We prove that an absolute minimum core(AMC)model consisting of a spin-glass 2D Ising model interacting with its nearest neighboring plane,has its computational complexity O(2mn).Any algorithms to make the model smaller(or simpler)than the AMC model will cut the basic element of the spin-glass 3D Ising model and lost many important information of the original model.Therefore,the computational complexity of the spin-glass 3D Ising model cannot be reduced to be less than O(2mn)by any algorithms,which is in subexponential time,superpolynomial.

An Introduction to the Computational Complexity of Matrix Multiplication

This article introduces the approach on studying the computational complexity of matrix multiplication by ranks of the matrix multiplication tensors.Basic results and recent developments in this area are reviewed.

Progress in Computational Complexity Theory

We briefly survey a number of important recent uchievements in Theoretical Computer Science （TCS）, especially Computational Complexity Theory. We will discuss the PCP Theorem, its implications to inapproximability on combinatorial optimization problems; space bounded computations, especially deterministic logspace algorithm for undirected graph connectivity problem; deterministic polynomial-time primality test; lattice complexity, worst-case to average-case reductions; pseudorandomness and extractor constructions; and Valiant＇s new theory of holographic algorithms and reductions.

ON THE COMPUTATIONAL COMPLEXITY OF THE MAXIMUM TRADE PROBLEM

Consider a computer assisted trading system in which the needs and the products of the traders are compared by a computer system and the trading proceeds without attaching a dollar price to each commodity. In such a system the computer serves as aii 'intelligent' communication link between traders, enhancing the ability of producers and consumers to exchange goods. In this paper, we examine one computational aspect of such computerized trading schemes:Given a list of trading proposals (each proposal specifying the quantities of the commodities to be traded),how should one arrange the trades so that the maximum number of trades can be made in the market? We show that this maximum trade problem is computationally hard; it is NP-complete (Nondeterministic Polynomial Time Complete). We then describe some related open questions and potential solutions.

Computationally efficient MUSIC based DOA estimation algorithm for FMCW radar

This paper proposes low-cost yet high-accuracy direction of arrival(DOA)estimation for the automotive frequency-modulated continuous-wave(FMcW)radar.The existing subspace-based DOA estimation algorithms suffer fromeither high computational costs or low accuracy.We aim to solve such contradictory relation between complexity and accuracy by using randomizedmatrix approximation.Specifically,we apply an easily-interpretablerandomized low-rank approximation to the covariance matrix(CM)and R∈C^(M×M)throughthresketch maties in the fom of R≈OBQ^(H).Here the approximately compute its subspaces.That is,we first approximate matrix Q∈C^(M×z)contains the orthonormal basis for the range of the sketchmatrik C∈C^(M×z)cwe whichis etrated fom R using randomized unifom counsampling and B∈C^(z×z)is a weight-matrix reducing the approximation error.Relying on such approximation,we are able to accelerate the subspacecomputation by the orders of the magnitude without compromising estimation accuracy.Furthermore,we drive a theoretical error bound for the suggested scheme to ensure the accuracy of the approximation.As validated by the simulation results,the DOA estimation accuracy of the proposed algorithm,eficient multiple signal classification(E-MUSIC)s high,closely tracks standardMUSIC,and outperforms the well-known algorithms with tremendouslyreduced time complexity.Thus,the devised method can realize high-resolutionreal-time target detection in the emerging multiple input and multiple output(MIMO)automotive radar systems.

A Method of Estimating Computational Complexity Based on Input Conditions for N-vehicle Problem

This paper proposes a method of estimating computational complexity of problem through analyzing its input condition for N-vehicle exploration problem. The N-vehicle problem is firstly formulated to determine the optimal replacement in the set of permutations of 1 to N. The complexity of the problem is factorial of N （input scale of problem）. To balance accuracy and efficiency of general algorithms, this paper mentions a new systematic algorithm design and discusses correspondence between complexity of problem and its input condition, other than just putting forward a uniform approximation algorithm as usual. This is a new technique for analyzing computation of NP problems. The method of corresponding is then presented. We finally carry out a simulation to verify the advantages of the method： 1） to decrease computation in enumeration; 2） to efficiently obtain computational complexity for any N-vehicle case; 3） to guide an algorithm design for any N-vehicle case according to its complexity estimated by the method.

Time Complexity of Evolutionary Algorithms for Combinatorial Optimization:A Decade of Results

Computational time complexity analyzes of evolutionary algorithms （EAs） have been performed since the mid-nineties. The first results were related to very simple algorithms, such as the （1＋1）-EA, on toy problems. These efforts produced a deeper understanding of how EAs perform on different kinds of fitness landscapes and general mathematical tools that may be extended to the analysis of more complicated EAs on more realistic problems. In fact, in recent years, it has been possible to analyze the （1＋1）-EA on combinatorial optimization problems with practical applications and more realistic population-based EAs on structured toy problems. This paper presents a survey of the results obtained in the last decade along these two research lines. The most common mathematical techniques are introduced, the basic ideas behind them are discussed and their elective applications are highlighted. Solved problems that were still open are enumerated as are those still awaiting for a solution. New questions and problems arisen in the meantime are also considered.

A novel low-complexity power allocation algorithm based on the NOMA system in a low-speed environment

For future wireless communication systems,Power Domain Non-Orthogonal Multiple Access(PD-NOMA)using an advanced receiver has been considered as a promising radio access technology candidate.Power allocation plays an important role in the PD-NOMA system because it considerably affects the total throughput and Geometric Mean User Throughput(GMUT)performance.However,most existing studies have not completely accounted for the computational complexity of the power allocation process when the User Terminals(UTs)move in a slow fading channel environment.To resolve such problems,a power allocation method is proposed to considerably reduce the search space of a Full Search Power(FSP)allocation algorithm.The initial power reallocation coefficients will be set to start with former optimal values by the proposed Lemma before searching for optimal power reallocation coefficients based on total throughput performance.Step size and correction granularity will be adjusted within a much narrower power search range while invalid power combinations may be reasonably discarded during the search process.The simulation results show that the proposed power reallocation scheme can greatly reduce computational complexity while the total throughput and GMUT performance loss are not greater than 1.5%compared with the FSP algorithm.

Computationally Efficient Direction of Arrival Estimation for Improved Nested Linear Array

Nested linear array enables to enhance localization resolution and achieve under-determined direction of arrival(DOA)estimation.In this paper,the traditional two-level nested linear array is improved to achieve more degrees of freedom(DOFs)and better angle estimation performance.Furthermore,a computationally efficient DOA estimation algorithm is proposed.The discrete Fourier transform(DFT)method is utilized to obtain coarse DOA estimates,and subsequently,fine DOA estimates are achieved by spatial smoothing multiple signals classification(SS-MUSIC)algorithm.Compared to SS-MUSIC algorithm,the proposed algorithm has the same estimation accuracy with lower computational complexity because the coarse DOA estimates enable to shrink the range of angle spectral search.In addition,the estimation of the number of signals is not required in advance by DFT method.Extensive simulation results testify the effectiveness of the proposed algorithm.

Computational Cluster with Entangled States

In this article the inherent computational power of the quantum entangled cluster states examined by measurement-based quantum computations is studied. By defining a common framework of rules for measurement of quantum entangled cluster states based on classical computations, the precise and detailed meaning of the computing power of the correlations in the quantum cluster states is made. This study exposes a connection, arousing interest, between the infringement of the realistic models that are local and the computing power of the quantum entangled cluster states.

Quantum Chemistry Based Computational Study on the Conformational Population of a Neodymium Neodecanoate Complex

The title complex is widely used as an efficient key component of Ziegler-Natta catalyst for stereospecific polymerization of dienes to produce synthetic rubbers. However, the quantitative structure-activity relationship（QSAR） of this kind of complexes is still not clear mainly due to the difficulties to obtain their geometric molecular structures through laboratory experiments. An alternative solution is the quantum chemistry calculation in which the comformational population shall be determined. In this study, ten conformers of the title complex were obtained with the function of molecular dynamics conformational search in Gabedit 2.4.8, and their geometry optimization and thermodynamics calculation were made with a Sparkle/PM7 approach in MOPAC 2012. Their Gibbs free energies at 1 atm. and 298.15 K were calculated. Population of the conformers was further calculated out according to the theory of Boltzmann distribution, indicating that one of the ten conformers has a dominant population of 77.13%.

Application and comparison of kernel functions for linear parameter varying model approximation of nonlinear systems

In this paper,a comparative study for kernel-PCA based linear parameter varying(LPV)model approximation of sufficiently nonlinear and reasonably practical systems is carried out.Linear matrix inequalities(LMIs)to be solved in LPV controller design process increase exponentially with the increase in a number of scheduling variables.Fifteen kernel functions are used to obtain the approximate LPV model of highly coupled nonlinear systems.An error to norm ratio of original and approximate LPV models is introduced as a measure of accuracy of the approximate LPV model.Simulation examples conclude the effectiveness of kernel-PCA for LPV model approximation as with the identification of accurate approximate LPV model,computation complexity involved in LPV controller design is decreased exponentially.

Triangular code:Near-optimal linear time fountain code

In this paper,we propose Triangular Code(TC),a new class of fountain code with near-zero redundancy and linear encoding and decoding computational complexities of OeLklog kT,where k is the packet batch size and L is the packet data length.Different from previous works where the optimal performance of codes has been shown under asymptotic assumption,TC enjoys near-zero redundancy even under non-asymptotic settings for smallmoderate number of packets.These features make TC suitable for practical implementation in batteryconstrained devices in IoT,D2D and M2M network paradigms to achieve scalable reliability,and minimize latency due to its low decoding delay.TC is a non-linear code,which is encoded using the simple shift and XOR addition operations,and decoded using the simple back-substitution algorithm.Although it is nonlinear code at the packet level,it remains linear code when atomized at the bit level.We use this property to show that the backsubstitution decoder of TC is equivalent to the Belief Propagation(BP)decoder of LT code.Therefore,TC can benefit from rich prolific literature published on LT code,to design efficient code for various applications.Despite the equivalency between the decoders of TC and LT code,we show that compared to state-of-the-art optimized LT code,TC reduces the redundancy of LT code by 68%-99% for k reaching 1024.

Appearance Based Dynamic Hand Gesture Recognition Using 3D Separable Convolutional Neural Network

Appearance-based dynamic Hand Gesture Recognition(HGR)remains a prominent area of research in Human-Computer Interaction(HCI).Numerous environmental and computational constraints limit its real-time deployment.In addition,the performance of a model decreases as the subject’s distance from the camera increases.This study proposes a 3D separable Convolutional Neural Network(CNN),considering the model’s computa-tional complexity and recognition accuracy.The 20BN-Jester dataset was used to train the model for six gesture classes.After achieving the best offline recognition accuracy of 94.39%,the model was deployed in real-time while considering the subject’s attention,the instant of performing a gesture,and the subject’s distance from the camera.Despite being discussed in numerous research articles,the distance factor remains unresolved in real-time deployment,which leads to degraded recognition results.In the proposed approach,the distance calculation substantially improves the classification performance by reducing the impact of the subject’s distance from the camera.Additionally,the capability of feature extraction,degree of relevance,and statistical significance of the proposed model against other state-of-the-art models were validated using t-distributed Stochastic Neighbor Embedding(t-SNE),Mathew’s Correlation Coefficient(MCC),and the McNemar test,respectively.We observed that the proposed model exhibits state-of-the-art outcomes and a comparatively high significance level.

Accelerate Single Image Super-Resolution Using Object Detection Process

Image Super-Resolution(SR)research has achieved great success with powerful neural networks.The deeper networks with more parameters improve the restoration quality but add the computation complexity,which means more inference time would be cost,hindering image SR from practical usage.Noting the spatial distribution of the objects or things in images,a twostage local objects SR system is proposed,which consists of two modules,the object detection module and the SR module.Firstly,You Only Look Once(YOLO),which is efficient in generic object detection tasks,is selected to detect the input images for obtaining objects of interest,then put them into the SR module and output corresponding High-Resolution(HR)subimages.The computational power consumption of image SR is optimized by reducing the resolution of input images.In addition,we establish a dataset,TrafficSign500,for our experiment.Finally,the performance of the proposed system is evaluated under several State-Of-The-Art(SOTA)YOLOv5 and SISR models.Results show that our system can achieve a tremendous computation improvement in image SR.

UAV flight strategy algorithm based on dynamic programming

Unmanned aerial vehicles(UAVs) may play an important role in data collection and offloading in vast areas deploying wireless sensor networks, and the UAV’s action strategy has a vital influence on achieving applicability and computational complexity. Dynamic programming(DP) has a good application in the path planning of UAV, but there are problems in the applicability of special terrain environment and the complexity of the algorithm.Based on the analysis of DP, this paper proposes a hierarchical directional DP(DDP) algorithm based on direction determination and hierarchical model. We compare our methods with Q-learning and DP algorithm by experiments, and the results show that our method can improve the terrain applicability, meanwhile greatly reduce the computational complexity.

Fast DOA estimation algorithm for MIMO sonar based on ant colony optimization

The maximum likelihood （ML） estimator demonstrates remarkable performance in direction of arrival （DOA） estimation for the multiple input multiple output （MIMO） sonar. However, this advantage comes with prohibitive computational complexity. In order to solve this problem, an ant colony optimization （ACO） is incorporated into the MIMO ML DOA estimator. Based on the ACO, a novel MIMO ML DOA estimator named the MIMO ACO ML （ML DOA estimator based on ACO for MIMO sonar） with even lower computational complexity is proposed. By extending the pheromone remaining process to the pheromone Gaussian kernel probability distribution function in the continuous space, the pro- posed algorithm achieves the global optimum value of the MIMO ML DOA estimator. Simulations and experimental results show that the computational cost of MIMO ACO ML is only 1/6 of the MIMO ML algorithm, while maintaining similar performance with the MIMO ML method.

Fuzzy inference systems with no any rule base and linearly parameter growth

A class of new fuzzy inference systems New-FISs is presented.Compared with the standard fuzzy system, New-FIS is still a universal approximator and has no fuzzy rule base and linearly parameter growth. Thus, it effectively overcomes the second "curse of dimensionality":there is an exponential growth in the number of parameters of a fuzzy system as the number of input variables,resulting in surprisingly reduced computational complexity and being especially suitable for applications,where the complexity is of the first importance with respect to the approximation accuracy.

Dynamic Routing Protocol for Computer Networkswith Clustering Topology

This paper presents a hierarchical dynamic routing protocol (HDRP) based on the discrete dynamic programming principle. The proposed protocol can adapt to the dynamic and large computer networks (DLCN) with clustering topology. The procedures for realizing routing update and decision are presented in this paper. The proof of correctness and complexity analysis of the protocol are also made. The performance measures of the HDRP including throughput and average message delay are evaluated by using of simulation. The study shows that the HDRP provides a new available approach to the routing decision for DLCN or high speed networks with clustering topology.