Search

Abstract Purpose Despite the many progresses with alignment algorithms, aligning divergent protein sequences with less than 20–35% pairwise identity (so called "twilight zone") remains a difficult problem. Many alignment algorithms have been using substitution matrices since their creation in the 1970’s to generate alignments, however, these matrices do not work well to score alignments within the twilight zone. We developed Protein Embedding based Alignments, or PEbA, to better align sequences with low pairwise identity. Similar to the traditional Smith-Waterman algorithm, PEbA uses a dynamic programming algorithm but the matching score of amino acids is based on the similarity of their embeddings from a protein language model. Methods We tested PEbA on over twelve thousand benchmark pairwise alignments from BAliBASE, each one extracted from one of their multiple sequence alignments. Five different BAliBASE references were used, each with different sequence identities, motifs, and lengths, allowing PEbA to showcase how well it aligns under different circumstances. Results PEbA greatly outperformed BLOSUM substitution matrix-based pairwise alignments, achieving different levels of improvements of the alignment quality for pairs of sequences with different levels of similarity (over four times as well for pairs of sequences with

The Cognitive Radio (CR) is an imminent technology, intended to make more effective use of the available spectrum by giving access to licensed frequency bands by unlicensed Secondary Users (SUs) without affecting Primary licensed Users (PUs). Depending on the region where the energy is being observed, each CR communicates local decisions or the seen energy to the Fusion Center (FC). This study presents the many plots that discuss an enhanced double threshold through the Cooperative Spectrum Sensing (CSS) approach. The FC then combines local decisions with the measured energy values to reach a final decision. The usage of several machine learning methods in spectrum decision with the myopic decision is estimated. The system seeks to enhance the long-term overall performance of the SU.

Purpose: Despite the many progresses with alignment algorithms, aligning divergent protein sequences with less than 20–35% pairwise identity (so called "twilight zone") remains a difficult problem. Many alignment algorithms have been using substitution matrices since their creation in the 1970’s to generate alignments, however, these matrices do not work well to score alignments within the twilight zone. We developed Protein Embedding based Alignments, or PEbA, to better align sequences with low pairwise identity. Similar to the traditional Smith-Waterman algorithm, PEbA uses a dynamic programming algorithm but the matching score of amino acids is based on the similarity of their embeddings from a protein language model. Methods: We tested PEbA on over twelve thousand benchmark pairwise alignments from BAliBASE, each one extracted from one of their multiple sequence alignments. Five different BAliBASE references were used, each with different sequence identities, motifs, and lengths, allowing PEbA to showcase how well it aligns under different circumstances. Results: PEbA greatly outperformed BLOSUM substitution matrix-based pairwise alignments, achieving different levels of improvements of the alignment quality for pairs of sequences with different levels of similarity (over four times as well for pairs of sequences with <10% identity). We also compared PEbA with embeddings generated by different protein language models (ProtT5 and ESM-2) and found that ProtT5- XL-U50 produced the most useful embeddings for aligning protein sequences. PEbA also outperformed DEDAL and vcMSA, two recently developed protein language model embedding-based alignment methods. Conclusion: Our results suggested that general purpose protein language models provide useful contextual information for generating more accurate protein alignments than typically used methods. [ABSTRACT FROM AUTHOR]

The Cognitive Radio (CR) is an imminent technology, intended to make more effective use of the available spectrum by giving access to licensed frequency bands by unlicensed Secondary Users (SUs) without affecting Primary licensed Users (PUs). Depending on the region where the energy is being observed, each CR communicates local decisions or the seen energy to the Fusion Center (FC). This study presents the many plots that discuss an enhanced double threshold through the Cooperative Spectrum Sensing (CSS) approach. The FC then combines local decisions with the measured energy values to reach a final decision. The usage of several machine learning methods in spectrum decision with the myopic decision is estimated. The system seeks to enhance the long-term overall performance of the SU. [ABSTRACT FROM AUTHOR]

The rapid advances in sequencing technology have led to an explosion of sequence data. Sequence alignment is the central and fundamental problem in many sequence analysis procedure, while local alignment is often the kernel of these algorithms. Usually, Smith–Waterman algorithm is used to find the best subsequence match between given sequences. However, the high time complexity makes the algorithm time-consuming. A lot of approaches have been developed to accelerate and parallelize it, such as vector-level parallelization, thread-level parallelization, process-level parallelization, and heterogeneous acceleration, but the current researches seem unsystematic, which hinders the further research of parallelizing the algorithm. In this paper, we summarize the current research status of parallel local alignments and describe the data layout in these work. Based on the research status, we emphasize large-scale genomic comparisons. By surveying some typical alignment tools' performance, we discuss some possible directions in the future. We hope our work will provide the developers of the alignment tool with technical principle support, and help researchers choose proper alignment tools. [ABSTRACT FROM AUTHOR]

This paper proposes the design and the implementation of a Spark parallelization plan for improving the Smith-Waterman (SW) algorithm, named the Spark-OSW algorithm. Then, the Spark-OSW was verified through accuracy, performance and acceleration tests. The results show that the proposed algorithm achieved 100% accuracy, ran much faster than the SW, and performed well in cluster environment. The research findings shed important new light on the database search for gene sequences.

Type III secretion systems (T3SS) can be found in many pathogenic bacteria, such as Dysentery bacillus , Salmonella typhimurium , Vibrio cholera and pathogenic Escherichia coli. The routes of infection of these bacteria include the T3SS transferring a large number of type III secreted effectors (T3SE) into host cells, thereby blocking or adjusting the communication channels of the host cells. Therefore, the accurate identification of T3SEs is the precondition for the further study of pathogenic bacteria. In this article, a new T3SEs ensemble predictor was developed, which can accurately distinguish T3SEs from any unknown protein. In the course of the experiment, methods and models are strictly trained and tested. Compared with other methods, EP3 demonstrates better performance, including the absence of overfitting, strong robustness and powerful predictive ability. EP3 (an ensemble predictor that accurately identifies T3SEs) is designed to simplify the user's (especially nonprofessional users) access to T3SEs for further investigation, which will have a significant impact on understanding the progression of pathogenic bacterial infections. Based on the integrated model that we proposed, a web server had been established to distinguish T3SEs from non-T3SEs, where have EP3_1 and EP3_2. The users can choose the model according to the species of the samples to be tested. Our related tools and data can be accessed through the link http://lab.malab.cn/∼lijing/EP3.html. [ABSTRACT FROM AUTHOR]

Background: Sequence alignment is a way of arranging sequences (e.g., DNA, RNA, protein, natural language, financial data, or medical events) to identify the relatedness between two or more sequences and regions of similarity. For Electronic Health Records (EHR) data, sequence alignment helps to identify patients of similar disease trajectory for more relevant and precise prognosis, diagnosis and treatment of patients.Methods: We tested two cutting-edge global sequence alignment methods, namely dynamic time warping (DTW) and Needleman-Wunsch algorithm (NWA), together with their local modifications, DTW for Local alignment (DTWL) and Smith-Waterman algorithm (SWA), for aligning patient medical records. We also used 4 sets of synthetic patient medical records generated from a large real-world EHR database as gold standard data, to objectively evaluate these sequence alignment algorithms.Results: For global sequence alignments, 47 out of 80 DTW alignments and 11 out of 80 NWA alignments had superior similarity scores than reference alignments while the rest 33 DTW alignments and 69 NWA alignments had the same similarity scores as reference alignments. Forty-six out of 80 DTW alignments had better similarity scores than NWA alignments with the rest 34 cases having the equal similarity scores from both algorithms. For local sequence alignments, 70 out of 80 DTWL alignments and 68 out of 80 SWA alignments had larger coverage and higher similarity scores than reference alignments while the rest DTWL alignments and SWA alignments received the same coverage and similarity scores as reference alignments. Six out of 80 DTWL alignments showed larger coverage and higher similarity scores than SWA alignments. Thirty DTWL alignments had the equal coverage but better similarity scores than SWA. DTWL and SWA received the equal coverage and similarity scores for the rest 44 cases.Conclusions: DTW, NWA, DTWL and SWA outperformed the reference alignments. DTW (or DTWL) seems to align better than NWA (or SWA) by inserting new daily events and identifying more similarities between patient medical records. The evaluation results could provide valuable information on the strengths and weakness of these sequence alignment methods for future development of sequence alignment methods and patient similarity-based studies. [ABSTRACT FROM AUTHOR]

Alarm floods can interfere with operators and may therefore cause or aggravate industrial accidents. A novel algorithm is proposed for pattern mining in multiple alarm floods. Unlike traditional methods which either cannot deal with multiple sequences with time stamps or suffer from high computational cost, the computational complexity of this proposed algorithm is reduced significantly by introducing a generalized pairwise sequence alignment method and a progressive multiple sequence alignment approach. Two types of alignment refinement methods are developed to improve the alignment accuracy. The effectiveness of the proposed algorithm is tested using a dataset from a real chemical plant. [ABSTRACT FROM AUTHOR]

In Bioinformatics, sequence alignment algorithm aims to find out whether biological sequences (e.g., DNA, RNA, or Protein sequences) are related or not. A variety of algorithms are developed, Smith–Waterman Algorithm (SW) is a well-known local alignment algorithm to find the similarity of two sequences and provides optimal result using dynamic programming. As the size of sequence database is doubling about every 6 months, the computational time also increases. Sequence alignment algorithms performance can have improved by using the parallel computing technology on the GPU. In this paper, we proposed a method to improve the performance of SW algorithm by using GPU's shared memory instead of global memory. By using shared memory, the data being transferred between the global memory and processing elements is reduced, which in turn improves the performance. The tabulated result showed positive sign of correctness in proposed method and tested using UniProt sequence database. [ABSTRACT FROM AUTHOR]

Smith–Waterman algorithm (SW) is a popular dynamic programming algorithm widely used in bioinformatics for local biological sequence alignment. Due to the O (n 2) high time and space complexity of SW and growing size of biological data, it is crucial to accelerate SW for high performance. In view of the GPU high efficiency in science computation, many existing studies (e.g., CUDAlign, CUDASW++) speedup SW with GPU. However, the strong data dependency makes SW communication intensive, and the previous works fail to fully leverage the heterogeneous capabilities of the GPU machine for either the neglect of the CPU ability or the low bandwidth of PCI-e. In this paper, we propose ASW, which aims at accelerating SW algorithm with accelerated processing unit (APU), a heterogeneous processor integrates CPU and GPU in a single die and share the same memory. This coupled CPU–GPU architecture is more suitable for frequent data exchanging due to the elimination of PCI-e bus. For the full utilization of both CPU and GPU in APU system, ASW partitions the whole SW matrix into blocks and dynamically dispatches each block to CPU and GPU for the concurrent execution. A DAG-based dynamic scheduling method is presented to dispatch the workload automatically. Moreover, we also design a time cost model to determine the partition granularity in the matrix division phase. We have evaluated ASW on AMD A12 platform and our results show that ASW achieves a good performance of 7.2 GCUPS (gigacells update per second). [ABSTRACT FROM AUTHOR]

Hard decision combination provides bandwidth efficiency but the results produced are unreliable while soft decision combination has better results but at the expense of much consumption of bandwidth. An acceptable trade-off is achieved between the two in case of quantized decision combination. In this paper an optimal quantization scheme is proposed in which the local sensing information is quantized so the maximum detection probability is met while the false alarm probability remains under a certain constraint. The proposed optimal scheme works on the basis of energy detection and the local quantization thresholds are found through iterative search. Smith-Waterman algorithm (SWA) is used to compare the local sensing reports of the CR users and similarity indexes are found for the CR users. The local sensing decisions of the CR users below a certain calculated threshold are rejected and are not included in the final decision combination at the FC. For detailed analysis, SWA-based rules of decision combination with optimal quantization thresholds are compared with a scheme that employs SWA-based rules of decision combination with heuristically selected quantization thresholds and a conventional majority combination scheme. Simulation results show that the proposed scheme performs better than the other two schemes. [ABSTRACT FROM AUTHOR]

The Smith–Waterman (SW) algorithm explores all the possible alignments between two or more sequences and as a result it returns the optimal local alignment. However, the computational cost of this algorithm is very high, and the exponential growth of computation makes SW unrealistic for searching similarities in large sets of sequences. Fortunately, the dynamic programming kernel of the SW algorithm involves mathematical operations over affine control loops whose iteration space can be represented by the polyhedral model. This allows us to apply polyhedral compilation techniques to optimize the studied SW dense array code. In this article, we present an approach to generate efficient SW implementations for two and three sequences by using the transitive closure of a dependence graph and loop skewing. Generated programs are represented with parallel tiled loop nests, which expose significantly higher performance than that of programs obtained with closely related compilers. The approach is able to tile all loops of original loop nests as opposed to well-known affine transformation techniques. Furthermore, it allows for code optimization of three-sequence alignment. Such a code cannot be generated by means of state-of-the-art automatic optimizing compilers. We demonstrate that an under-approximation of transitive closure (instead of exact transitive closure) can be used to generate valid parallel tiled code. This considerably reduces the computational complexity of the approach. Generated codes were run on cores of a modern Intel multiprocessor and they expose high speedup and good scalability on this platform. [ABSTRACT FROM AUTHOR]

Sequence alignment is one of the fundamental problems in computational biology and has numerous applications. The Smith–Waterman algorithm generates optimal local alignment for pairwise alignment task and has become a standard algorithm in its field. However, the current version of the Smith–Waterman algorithm demands a significant amount of memory and is not suitable for alignment of very long sequences. On the hand, the recent DNA sequencing technologies have produced vast amounts of biological sequences. Some nucleic acid sequences are very long and cannot employ the Smith–Waterman algorithm. To this end, this study proposes the PAAVLS algorithm that follows the dynamic programming technique employed by the Smith–Waterman algorithm and largely reduces the demand of memory. The proposed PAAVLS algorithm can be employed for alignment of very long sequences, i.e., sequences contain more than 100,000,000 nucleotides, on a personal computer. Additionally, the running time of the proposed PAAVLS algorithm is comparable with the running time of the standard Smith–Waterman algorithm. [ABSTRACT FROM AUTHOR]

Since a smart distribution grid has a diversity of components and complicated topology; it is very hard to achieve fault early warning for each part. A fault early warning model for smart distribution grid combining a back propagation (BP) neural network with a gene sequence alignment algorithm is proposed. Firstly; the operational state of smart distribution grid is divided into four states; and a BP neural network is adopted to explore the operational state from the historical fault data of the smart distribution grid. This obtains the relationship between each state transition time sequence and corresponding fault, and is used to construct the fault gene table. Then; a state transition time sequence is obtained online periodically, which is matched with each gene in fault gene table by an improved Smith-Waterman algorithm. If the maximum match score exceeds the given threshold, the relevant fault will be detected early. Finally, plenty of time domain simulation is performed on the proposed fault early warning model to IEEE-14 bus. The simulation results show that the proposed model can achieve efficient early fault warning of smart distribution grids. [ABSTRACT FROM AUTHOR]

In the last decade, Data mining techniques have been applied for sensor data in a wide range of applications. Like health care monitoring systems, manufacturing process. Intruder detection, database management and other. A lot of data mining engineering is based on the calculation of the similarity between two models of sensor data. A number of representations and Equality measures for multi - assign time series was suggested in the literature. In this paper, we describe a new way of calculating whether two similarities in the series of multiple series are based on the temporal version of Smith-Waterman (SW), a known information algorithm. Next, we apply our method to detect data on the demand for care of the elderly to early detection of the disease. Our procedure absorber is difficulties linked to the data uncertainty and aggregation that often occurs during treatment sensor data. The trials will take place one aging-in-place installation, Tiger Place placed in Columbia, MO. To validate our method we used data on nine no-portable a sensor for one-p located in TigerPlace apartments, combined with information of one Electronic Health Record (EHR).We deliver a set of experiments studying the temporal version of SW properties, with experiences on TigerPlace dataset. [ABSTRACT FROM AUTHOR]

The number of protein structures in the PDB database has been increasing more than 15-fold since 1999. The creation of computational models predicting enzymatic function is of major importance since such models provide the means to better understand the behavior of newly discovered enzymes when catalyzing chemical reactions. Until now, single-label classification has been widely performed for predicting enzymatic function limiting the application to enzymes performing unique reactions and introducing errors when multi-functional enzymes are examined. Indeed, some enzymes may be performing different reactions and can hence be directly associated with multiple enzymatic functions. In the present work, we propose a multi-label enzymatic function classification scheme that combines structural and amino acid sequence information. We investigate two fusion approaches (in the feature level and decision level) and assess the methodology for general enzymatic function prediction indicated by the first digit of the enzyme commission (EC) code (six main classes) on 40,034 enzymes from the PDB database. The proposed single-label and multi-label models predict correctly the actual functional activities in 97.8% and 95.5% (based on Hamming-loss) of the cases, respectively. Also the multi-label model predicts all possible enzymatic reactions in 85.4% of the multi-labeled enzymes when the number of reactions is unknown. Code and datasets are available at https://figshare.com/s/a63e0bafa9b71fc7cbd7.

Alarm flood is a serious hazard for industrial processes, alarm management techniques such as delay timers and dead-bands often are incapable of suppressing alarm floods because of the existence of consequence alarms. However, this problem could be handled by alarm flood analysis, which could help find the root cause, locate badly designed part in alarm systems and predict incoming alarm floods. In this paper we propose a method for pattern mining in multiple alarm flood sequences by extending a time-stamp adapted Smith–Waterman algorithm to the case with multiple sequences, making up one of the missing steps in alarm flood analysis. The technique involves the following new elements: similarity scoring functions, a dynamic programming equation, a back tracking procedure, and an alignment generation method. A dataset from an actual petrochemical plant has been used to test the effectiveness of the proposed algorithm. [ABSTRACT FROM AUTHOR]

This paper report a SW software version implementation in FPGA. The implementation was carried out using Altera DE2-115 EP4CE115F29C7 FPGA development board. Thirty eight tests with ranging from 1 to 2048 base-pair were used as to measure software version runtime which operating at two different clock frequency; 50MHz and 100MHz respectively. It shows that, the average runtime per cell for 100MHz and 50MHz are recorded at 0.021447ms and 0.044553ms per cell respectively. Therefore, we can conclude that the runtime is depending on the iterative computational method used and the higher frequency can improve the overall runtime performance. [ABSTRACT FROM AUTHOR]

This paper report a SW software version implementation in FPGA. The implementation was carried out using Altera DE2-115 EP4CE115F29C7 FPGA development board. Thirty eight tests with ranging from 1 to 2048 base-pair were used as to measure software version runtime which operating at two different clock frequency; 50MHz and 100MHz respectively. It shows that, the average runtime per cell for 100MHz and 50MHz are recorded at 0.021447ms and 0.044553ms per cell respectively. Therefore, we can conclude that the runtime is depending on the iterative computational method used and the higher frequency can improve the overall runtime performance. [ABSTRACT FROM AUTHOR]