Search

This work presents the method for traffic analysis based on the Needleman–Wunsch global algorithm of sequence alignment. A prototype of the intrusion detection system for the Internet of Things has been developed. Results of the experiments show the proposed approach is promising.

This paper attempts to overcome the inefficiency of covariance model (CM) in the search for non-coding sequence. For this purpose, the members of non-coding RNA family were compared and the CM of the family was discussed in details. Next, the CM was improved for structural units in the secondary structure, through the addition of the upper and lower limits on subsequence length. Based on the length distribution of each structural unit, the improved model limits the number of insertions and deletions during the evolution of sequences in the same family. After that, the author put forward a novel non-coding RNA sequence alignment algorithm. The experimental results show that the proposed algorithm can greatly reduce the computing time of non-coding RNA sequence comparison.

In this work, we review two alternative Processing-in-Memory (PIM) accelerators based on Spin-Orbit-Torque Magnetic Random Access Memory (SOT-MRAM) to execute DNA short read alignment based on an optimized and hardware-friendly alignment algorithm. We first discuss the reconstruction of the existing sequence alignment algorithm based on BWT and FM-index such that it can be fully implemented leveraging PIM functions. We then transform SOT-MRAM array to a potential computational memory by presenting two different reconfigurable sense amplifiers to accelerate the reconstructed alignment-in-memory algorithm. The cross-layer simulation results show that such PIM platforms are able to achieve a nearly ten-fold and two-fold increases in throughput/power/area measure compared with recent ASIC and processing-in-ReRAM designs, respectively.

Motivation From evolutionary interference, function annotation to structural prediction, protein sequence comparison has provided crucial biological insights. While many sequence alignment algorithms have been developed, existing approaches often cannot detect hidden structural relationships in the ‘twilight zone’ of low sequence identity. To address this critical problem, we introduce a computational algorithm that performs protein Sequence Alignments from deep-Learning of Structural Alignments (SAdLSA, silent ‘d’). The key idea is to implicitly learn the protein folding code from many thousands of structural alignments using experimentally determined protein structures. Results To demonstrate that the folding code was learned, we first show that SAdLSA trained on pure α-helical proteins successfully recognizes pairs of structurally related pure β-sheet protein domains. Subsequent training and benchmarking on larger, highly challenging datasets show significant improvement over established approaches. For challenging cases, SAdLSA is ∼150% better than HHsearch for generating pairwise alignments and ∼50% better for identifying the proteins with the best alignments in a sequence library. The time complexity of SAdLSA is O(N) thanks to GPU acceleration. Availability and implementation Datasets and source codes of SAdLSA are available free of charge for academic users at http://sites.gatech.edu/cssb/sadlsa/. Supplementary information Supplementary data are available at Bioinformatics online.

In this paper, we propose a high-throughput and energy-efficient Processing-in-Memory accelerator (PIM-Aligner) to execute DNA short read alignment based on an optimized and hardware-friendly alignment algorithm. We first reconstruct the existing sequence alignment algorithm based on BWT and FM-index such that it can be fully implemented in PIM platforms. It supports exact alignment and also handles mismatches to reduce excessive backtracking. We then develop PIM-Aligner platform that transforms SOT-MRAM array to a potential computational memory to accelerate the reconstructed alignment-in-memory algorithm incurring a low cost on top of original SOT-MRAM chips (less than 10% of chip area). Accordingly, we present a local data partitioning, mapping, and pipeline technique to maximize the parallelism in multiple computational sub-array while doing the alignment task. The simulation results show that PIM-Aligner outperforms recent platforms based on dynamic programming with ∼ 3.1× higher throughput per Watt. Besides, PIM-Aligner improves the short read alignment throughput per Watt per mm2 by ∼ 9× and 1.9× compared to FM-index-based ASIC and processing-in-ReRAM designs, respectively.

The paper suggests a quantitative assessment of human movements using inexpensive 3D sensor technology and evaluates its accuracy by comparing it with human expert assessments. The two assessment methods show a high agreement. To achieve this, a novel sequence alignment algorithm was developed that works for arbitrary time series.

Software plagiarism cheats students out of their own education and leads to unfair grading, making software plagiarism detection an important problem. However, many popular plagiarism detection tools are inaccurate, language-specific, or closed source, limiting their applicability. In this work, we seek to address these problems via a novel approach. We adapt the optimal Smith-Waterman sequence alignment algorithm to precisely measure the similarity between programs, greatly improving detection accuracy relative to competitors. Our approach is applicable to any language describable by an ANTLR grammar, which includes most programming languages. We also provide a new type of evaluation based on random program generation and obfuscation. Finally, we make our approach freely available, allowing for customizations and transparent reasoning about detection behavior.

In order to improve the detection efficiency of SQL injection attack, this paper proposes a detection method of SQL injection attack based on sequence alignment algorithm. Needleman-Wunsch and its improved algorithm are used to carry out sequence alignment and then find out the best alignment results in the global-scope. Experiments show that 100% of the SQL injection attacks tested are detected in the detection rate; the algorithm has the minimum response delay compared with other types of SQL injection attacks. The detection method proposed in this paper can improve the detection effect quickly and effectively, and reduce the complexity of time and space.

In court proceedings, the question often arises: how much correspondence is there exactly between disputed writing and comparative writing patterns? According to handwriting examiners, handwriting cannot be measured in numbers. One of the reasons is that the handwriting experts use only a small part of the full feature complex, it is impossible to find and compare all of them manually. The selection is based on the expert’s experience, although contradictory opinions on the same test material can be given by different experts. Thus, the enhancement of expert objectivity in the court processes is highly desirable, my goal is to search for opportunities of application of computer science and approaches. The Soviet-type handwriting expertise methodology that is currently used in Hungary primarily interpreted the writing as a movement. In fact, traditional writing comparison treats handwriting as a moving stream. This observation led to the analysis of handwriting using the sequence matching method. This paper provides an example of how a sequence alignment algorithm for comparing DNA sequences can be used to compare handwriting. The suitability of the algorithm is illustrated by the fitting of fake and genuine signatures, and the expert opinion is based on numerical results on the value of the alignment.

Next Generation Sequencing (NGS) technology has become an indispensable tool for studying genomics, resulting in an exponentially growth of biological data. Booming data volume demands significant computational resources and creates challenges for 'Sequence Alignment', which is the most fundamental application in bioinformatics. Consequently, many researchers exploit both software and hardware methods to accelerate the most widely used sequence alignment algorithm - Basic Local Alignment Search Tool (BLAST). However, prior work suffers from moving huge DNA databases from the storage to computational units. Such data movement is both time and energy consuming. Based on the observation that the bottlenecks of BLAST involve a large amount of comparison operations, we propose a 3D Resistive Random Access Memory (ReRAM) based DNA Alignment Accelerator Architecture (RADAR) which performs most computational operations locally without moving DNA databases. To improve the storage density for various lengths of DNA sequences without damaging the performance, we propose a dense data mapping scheme to handle DNA sequences efficiently and a Tail Bits Duplication (TBD) technique to enable fully parallel computation for RADAR. Experimental results show that RADAR can achieve 5114x speedup and 386x energy reduction when compared to a single CPU. Compared to the Multi-Core/FPGA/GPU based accelerators, RADAR outperforms them between 53x and 1896x in processing speed.

Aiming at the problem that the result of some attack sequence alignment methods is not necessarily the optimal expression of their characteristics. This paper presents a Production Rule Sequence Alignment Algorithm (PRSA) combining the production rule inference mechanism which improves traditional sequence alignment algorithm. A new accumulation of knowledge is obtained by changing the way of sequence alignment and the transformation of signatures. PRSA overcomes the problem that the extraction results produced by the traditional sequence alignment algorithm cannot express the attack signature accurately. Then, we establish an automatic attack signature generation model based on PRSA. The experimental results show that the matching results obtained by using PRSA can express the signatures of the attack accurately and improve the detection rate of the attacks.

Eukaryotic genomes contain a significant fraction of repeats, which have very important biomedical function. Thus, aligning repeats from short sequences back to reference genome is the key step for further genome analysis. Unfortunately, the current aligning algorithms performed poorly in distinguishing repeats and nonrepeats. To this end, we proposed a new algorithm, named HashRepAligner, to address this problem. Finally, the cross comparison with other algorithms was performed, and the results indicated that HashRepAligner outperformed other aligners in terms of the detecting repeats.

International audience; Although there have been a large body of works on computing the similarity of static shapes, similarity judgments on deforming meshes are not studied well. In this study, we investigate a similarity measurement method for comparing two deforming meshes. Based on the degree of deformation, we first binarily label each triangle within each frame as either 'deformed' or 'rigid', then merge the 'deformed' triangles in both spatial and temporal domains for the segmentation. The segmentation results are encoded in a form of evolving graph, with an aim of obtaining a compact representation of the motion of the mesh. Finally, we formulate the similarity measurement as a sequence matching problem: after clustering similar graphs and assigning each of the graphs with the cluster labels, each deforming mesh is represented with a sequence of labels. Then, we apply a sequence alignment algorithm to compute the locally optimal alignment between the two label sequences, and to compute the similarity by normalizing the alignment score. The experimental results over several datasets show that the similarities of animation data can be captured correctly using our approach. This may be significant, as it solves a problem that cannot be handled by current approaches.

Sequence alignment is a widely-used tool in genomics. With the development of next generation sequencing (NGS) technology, the production of sequence read data has recently increased. A number of read alignment algorithms for handling NGS data have been developed. However, these algorithms suffer from a trade-off between the throughput and alignment quality, due to the large computational costs for processing repeat reads. Conversely, alignment algorithms with distributed systems such as Hadoop and Trinity can obtain a better throughput than existing algorithms on single machine without compromising the alignment quality. In this paper, we suggest BulkAligner, a novel sequence alignment algorithm on the graph-based in-memory distributed system Trinity. We covert the original reference sequence into graph form and perform sequence alignment by finding the longest paths on the graph. Our experimental results show that BulkAligner has at least an 1.8× and up to 57× better throughput with the same, or higher quality than existing algorithms with Hadoop. We analyze the scalability and show that we can obtain a better throughput by simply adding machines.

Detecting similarities between sequences is an important part of Bioinformatics. In this poster, we explore the use of high-level synthesis tool and a field-programmable gate array (FPGA) for optimizing a sequence alignment algorithm. We demonstrate the optimization techniques to improve the performance of the extended sequence alignment algorithm in the BWA software package, a tool for mapping DNA sequences against a large reference sequence. Applying the optimizations to the algorithm using Xilinx SDAccel OpenCL-to-FPGA tool, we reduce the kernel execution time from 62.8 ms to 0.45 ms while the power consumption is approximately 11 Watts on the ADM-PCIE-8K5 FPGA platform.

Biomolecular sequence alignment is an important research area in bioinformatics. Based on Flower Pollination Algorithm (FPA), we have proposed a new sequence alignment algorithm, named Pairwise Sequence Alignment with Flower Pollination Algorithm (PSAFPA). PSAFPA helps in finding the optimal or near-optimal solution to sequence alignment problem. PSAFPA first finds the current best solution with the help of FPA and then divides this solution into various segments of non-matching regions to find the better results. These segments are rearranged using FPA and finally the best identity value of each segment is added into the current best solution to get the final alignment identity value. Such segmentation helped to get better results. We have also done comparison of PSAFPA with the well-known methods using various DNA sequence pairs, which resulted in to better performance of PSAFPA for a majority of sequence pairs.

Motivation: Mapping of high-throughput sequencing data and other bulk sequence comparison applications have motivated a search for high-efficiency sequence alignment algorithms. The bit-parallel approach represents individual cells in an alignment scoring matrix as bits in computer words and emulates the calculation of scores by a series of logic operations composed of AND, OR, XOR, complement, shift and addition. Bit-parallelism has been successfully applied to the longest common subsequence (LCS) and edit-distance problems, producing fast algorithms in practice. Results: We have developed BitPAl, a bit-parallel algorithm for general, integer-scoring global alignment. Integer-scoring schemes assign integer weights for match, mismatch and insertion/deletion. The BitPAl method uses structural properties in the relationship between adjacent scores in the scoring matrix to construct classes of efficient algorithms, each designed for a particular set of weights. In timed tests, we show that BitPAl runs 7–25 times faster than a standard iterative algorithm. Availability and implementation: Source code is freely available for download at http://lobstah.bu.edu/BitPAl/BitPAl.html . BitPAl is implemented in C and runs on all major operating systems. Contact : jloving@bu.edu or yhernand@bu.edu or gbenson@bu.edu Supplementary information : Supplementary data are available at Bioinformatics online.

Sequence Alignment is an important means to study the function, evolution and similarity of biological sequences. There are a lot of Sequence Alignment algorithms available for free, but it's not easy to access, call and use. In this article, we analyzed the characteristics of each Sequence Alignment algorithm for digging the different advantages. Then they were integrated into a Web-based Sequence Alignment Platform which provides comfortable Human-Computer Interaction and convenient manual. Based on this platform, we implemented several experiments for testing performance. It is convenience to compare several algorithms at the same time.

A computer-aided method to design a hybrid layout—tree-shape planar flowlines is presented. In newtype flowshop layout, the common machines shared by several flowlines could be located together in functional sections. The approach combines traditional cell formation techniques with sequence alignment algorithms. Firstly, a sequence analysis based cell formation procedure is adopted; then the operation sequences for parts are aligned to maximize machines adjacency in hyperedge representations; finally a tree-shape planar flowline will be obtained for each part family. With the help of a sample of operation sequences obtained from industry, this algorithm is illustrated.

In the last ten years, high-performance and massively parallel computing technology comes into a high speed developing phase and is used in all fields. The cluster computer systems are also being widely used for their low cost and high performance. In bioinformatics research, solving a problem with computer usually takes hours even days. To speed up research, high-performance cluster computers are considered to be a good platform. Moving into the new MPP (massively parallel processing) system, the original algorithm should be parallelized in a proper way. In this paper, a new parallelizing method of useful sequence alignment algorithm (Smith-Waterman) is designed based on its optimizing algorithm already exists. The result is gratifying.

This short paper describes our three submissions to the 2015 edition of the MIREX Symbolic Melodic Similarity task. They all rely on a geometric model that represents melodies as spline curves in the pitch-time plane. The similarity between two melodies is then computed with a sequence alignment algorithm between sequences of spline spans: the more similar the shape of the curves, the more similar the melodies they represent. All submissions are the same we submitted last year, so they can serve as baseline to new submissions. This work was supported by an A4U postdoctoral grant and a Juan de la Cierva postdoctoral fellowship.

Due to the increasing requirements of the seamless and round-the-clock Location-based services (LBSs), a growing interest in Wi-Fi network aided location tracking is witnessed in the past decade. One of the significant problems of the conventional Wi-Fi location tracking approaches based on received signal strength (RSS) fingerprinting is the time-consuming and labor intensive work involved in location fingerprint calibration. To solve this problem, a novel unlabeled Wi-Fi simultaneous localization and mapping (SLAM) approach is developed to avoid the location fingerprinting and additional inertial or vision sensors. In this approach, an unlabeled mobility map of the coverage area is first constructed by using the crowd-sourcing from a batch of sporadically recorded Wi-Fi RSS sequences based on the spectral cluster assembling. Then, the sequence alignment algorithm is applied to conduct location tracking and mobility map updating. Finally, the effectiveness of this approach is verified by the extensive experiments carried out in a campus-wide area.

This paper discovers the major shortcomings of the Levenshtein Distance method, the longest common subsequence LCS method, and other general approaches to finding common parts, including the unjustified fragmentation of selected parts, the lack of sensitivity to transposition of large blocks, and no mechanisms to prevent accidental matches. The belief function theory leads to a flexible framework for similarity evaluation.The framework is aimed on new similarity models which are free of described shortcomings and can be effectively calculated. A sketch of better sequence alignment algorithm illustrates the framework's utility.

An algorithm for aligning biological sequences is presented that is an adaptation of the sequence generating function approach used in the statistical mechanics of biopolymers. This algorithm uses recursion relationships developed from a partition function formalism of alignment probabilities. It is implemented within a dynamic programming format that closely resembles the forward algorithm used in hidden Markov models (HMM). The algorithm aligns sequences or structures according to the statistically dominant alignment path and will be referred to as the SDP algorithm. An advantage of this method over previous ones is that it allows more complicated and physically realistic gap penalty functions to be incorporated into the algorithm in a facile manner. The performance of this algorithm in a case study of aligning the heavy and light chain from the variable region of an immunoglobulin is investigated.

Background: Uncharacterized proteins from newly sequenced genomes provide perfect targets for fold and function prediction. Results: For 38% of the entire genome of Mycoplasma genitalium , sequence similarity to a protein with a known structure can be recognized using a new sequence alignment algorithm. When comparing genomes of M. genitalium and Escherichia coli , > 80% of M. genitalium proteins have a significant sequence similarity to a protein in E. coli and there are > 40 examples that have not been recognized before. For all cases of proteins with significant profile similarities, there are strong analogies in their functions, if the functions of both proteins are known. The results presented here and other recent results strongly support the argument that such proteins are actually homologous. Assuming this homology allows one to make tentative functional assignments for > 50 previously uncharacterized proteins, including such intriguing cases as the putative β -lactam antibiotic resistance protein in M. genitalium. Conclusions: Using a new profile-to-profile alignment algorithm, the three-dimensional fold can be predicted for almost 40% of proteins from a genome of the small bacterium M. genitalium , and tentative function can be assigned to almost 80% of the entire genome. Some predictions lead to new insights about known functions or point to hitherto unexpected features of M.genitalium

With the rapid development of DNA sequencer, the rate of data generation is rapidly outpacing the rate at which it can be computationally processed. Traditional sequence alignment based on PC cannot fulfill the increasing demand. Accelerating the algorithm using FPGA provides the better performance compared to the other platforms. This paper will explain and classify the current sequence alignment algorithms. In addition, we analyze the different types of sequence alignment algorithms and present the taxonomy of FPGA-based sequence alignment implementations. This work will conclude the current solutions and provide a reference to further accelerating sequence alignment on a FPGA-based heterogeneous architecture.

Spatial relations are the main part of geographical information in natural language. Their extraction and semantic interpretation play a significant role in bridging the gap between geographical information system and natural language. Normally spatial relations are described with certain spatial terms and syntactic rules in natural language. To overcome the disadvantage of manual induction of syntactic rules, this paper proposes a new machine learning approach based on a sequence alignment algorithm. Firstly, the description instances of spatial relations in a large-scale annotated corpus are extracted and analyzed, and the sequence alignment algorithm is used to calculate the pattern similarity between instances of spatial relations. Then, the instances with high similarity are generalized aspopularly used syntactic rules. Finally, these rules are used for extraction spatial relations in a test data to evaluate their validation. The experimental results indicate that the generalized rules can achieve better performance than those rules induced according to occurrence frequency in the corpus.

Next Generation Sequencing (NGS) platforms typically produce short reads of size 50–150 base pairs (bp). The number of such short reads can be up to 6 billion per run. To align these short reads to a large genome is a computationally challenging problem. In this paper, we address this problem by considering the design and optimization of parallel sequence alignment on GPU based hybrid architectures. Even though the sequence alignment algorithm is inherently data-parallel, issues such as (a) space-time trade-offs in the Indexing schema, (b) need for fast candidate location search (CAL) on GPU, (c) maintaining low divergence along with low space for the dynamic programming based local alignment, make this a very challenging problem. We present the design of our novel parallel algorithm Graphics processor Accelerated BFAST (GrABFAST) for large scale read alignment that overcomes these challenges and demonstrates superior performance compared to Intel multi-core architectures. Using 5 large genomes including those of Humans, Maize, Horse, Dog and Bacteria, we demonstrate a speedup of around 6x using Fermi Tesla C2070 GPUs vs the BFAST algorithm on 16 core Intel Xeon 5570 architecture.

This paper presents a fast algorithm for sequence alignment in Biocomputing using Bloom filters. The idea behind this proposed method is comparing subsequence of incoming sequences with Bloom filter and discovering the matched subsequence. The sequence alignment problem has a large number of comparisons. According to the last successful experiences of useing Bloom filter in similar issues such as web search, it seems that using Bloom filter to solving this problem can be an appropriate solution. To evaluate the proposed algorithm, it has been implemented and compared to the Needleman-Wunsch method. Results show that in average, outpout quality is improved by 41%, memory usage by 84%, and response time by 52% compared to Needleman-Wunsch method are improved. In addition, for real samples, output quality is almost equivalent, memory usage is improved by 95% and response time by 40% compared to the Needleman-Wunsch method.

Sequence alignment is a very important problem in Bioinformatics since it is very useful to discover relationships among biological sequences. In this article we propose a new sequence alignment algorithm that is able to identify sequence similarities in linear space. Our solution is capable of using several parameters specifying in which conditions a given residue can be aligned. This decision is taken based on a perceptron neuron and the best set of parameters is found using simulated annealing. Comparing our algorithm to a well established algorithm, we found that for pairwise alignments, our approach was faster for all instances tested with speedups up to 7.63 and yields better quality results for the majority of the instances.

Background The Monte Carlo simulation of sequence evolution is routinely used to assess the performance of phylogenetic inference methods and sequence alignment algorithms. Progress in the field of molecular evolution fuels the need for more realistic and hence more complex simulations, adapted to particular situations, yet current software makes unreasonable assumptions such as homogeneous substitution dynamics or a uniform distribution of indels across the simulated sequences. This calls for an extensible simulation framework written in a high-level functional language, offering new functionality and making it easy to incorporate further complexity. Results PhyloSim is an extensible framework for the Monte Carlo simulation of sequence evolution, written in R, using the Gillespie algorithm to integrate the actions of many concurrent processes such as substitutions, insertions and deletions. Uniquely among sequence simulation tools, PhyloSim can simulate arbitrarily complex patterns of rate variation and multiple indel processes, and allows for the incorporation of selective constraints on indel events. User-defined complex patterns of mutation and selection can be easily integrated into simulations, allowing PhyloSim to be adapted to specific needs. Conclusions Close integration with R and the wide range of features implemented offer unmatched flexibility, making it possible to simulate sequence evolution under a wide range of realistic settings. We believe that PhyloSim will be useful to future studies involving simulated alignments.

This paper presents the design and implementation of the most parameterisable field-programmable gate array (FPGA)-based skeleton for pairwise biological sequence alignment reported in the literature. The skeleton is parameterised in terms of the sequence symbol type, i.e., DNA, RNA, or protein sequences, the sequence lengths, the match score, i.e., the score attributed to a symbol match, mismatch or gap, and the matching task, i.e., the algorithm used to match sequences, which includes global alignment, local alignment, and overlapped matching. Instances of the skeleton implement the Smith-Waterman and the Needleman-Wunsch algorithms. The skeleton has the advantage of being captured in the Handel-C language, which makes it FPGA platform-independent. Hence, the same code could be ported across a variety of FPGA families. It implements the sequence alignment algorithm in hand using a pipeline of basic processing elements, which are tailored to the algorithm parameters. This paper presents a number of optimizations built into the skeleton and applied at compile-time depending on the user-supplied parameters. These result in high performance FPGA implementations tailored to the algorithm in hand. For instance, actual hardware implementations of the Smith-Waterman algorithm for Protein sequence alignment achieve speedups of two orders of magnitude compared to equivalent standard desktop software implementations.

This paper describes the participation of the Technical University of Catalonia in the CLEF 2008 Question Answering on Speech Transcripts track. We have participated in the English and Spanish scenarios of QAst. For the processing of manual transcripts we have deployed a robust factoid Question Answering that uses minimal syntactic information. For the handling of automatic transcripts we modify the QA system with a Passage Retrieval and Answer Extraction engine based on a sequence alignment algorithm that searches for "sounds like" sequences. We perform a detailed analysis of our results and draw conclusions relating QA performance to word error rate in transcripts.

In this paper, we describe our approach to the TRECVID 2008 BBC Rushes Summarization task. First, we remove junk frames and dynamically accelerate videos according to their motion activity to maximize the content per time unit. Then, we search identical sequences using a sequence alignment algorithm derived from bio-informatics and we identify and structure scenes in videos, then we select one take per scene. We select the most relevant sequences in order to maximize the content and finally, we compose our summary in an original presentation. The produced summaries have been evaluated in the TRECVID campaign.