To see the other types of publications on this topic, follow the link: Alignment algorithm.
Journal articles on the topic 'Alignment algorithm'
Create a spot-on reference in APA, MLA, Chicago, Harvard, and other styles
Consult the top 50 journal articles for your research on the topic 'Alignment algorithm.'
Next to every source in the list of references, there is an 'Add to bibliography' button. Press on it, and we will generate automatically the bibliographic reference to the chosen work in the citation style you need: APA, MLA, Harvard, Chicago, Vancouver, etc.
You can also download the full text of the academic publication as pdf and read online its abstract whenever available in the metadata.
Browse journal articles on a wide variety of disciplines and organise your bibliography correctly.
1
Hung, Che-Lun, and Yaw-Ling Lin. "Implementation of a Parallel Protein Structure Alignment Service on Cloud." International Journal of Genomics 2013 (2013): 1–8. http://dx.doi.org/10.1155/2013/439681.
Full textAbstract:
Protein structure alignment has become an important strategy by which to identify evolutionary relationships between protein sequences. Several alignment tools are currently available for online comparison of protein structures. In this paper, we propose a parallel protein structure alignment service based on the Hadoop distribution framework. This service includes a protein structure alignment algorithm, a refinement algorithm, and a MapReduce programming model. The refinement algorithm refines the result of alignment. To process vast numbers of protein structures in parallel, the alignment and refinement algorithms are implemented using MapReduce. We analyzed and compared the structure alignments produced by different methods using a dataset randomly selected from the PDB database. The experimental results verify that the proposed algorithm refines the resulting alignments more accurately than existing algorithms. Meanwhile, the computational performance of the proposed service is proportional to the number of processors used in our cloud platform.
2
WANG, YI, and KUO-BIN LI. "MULTIPLE SEQUENCE ALIGNMENT USING AN EXHAUSTIVE AND GREEDY ALGORITHM." Journal of Bioinformatics and Computational Biology 03, no. 02 (April 2005): 243–55. http://dx.doi.org/10.1142/s021972000500103x.
Full textAbstract:
We describe an exhaustive and greedy algorithm for improving the accuracy of multiple sequence alignment. A simple progressive alignment approach is employed to provide initial alignments. The initial alignment is then iteratively optimized against an objective function. For any working alignment, the optimization involves three operations: insertions, deletions and shuffles of gaps. The optimization is exhaustive since the algorithm applies the above operations to all eligible positions of an alignment. It is also greedy since only the operation that gives the best improving objective score will be accepted. The algorithms have been implemented in the EGMA (Exhaustive and Greedy Multiple Alignment) package using Java programming language, and have been evaluated using the BAliBASE benchmark alignment database. Although EGMA is not guaranteed to produce globally optimized alignment, the tests indicate that EGMA is able to build alignments with high quality consistently, compared with other commonly used iterative and non-iterative alignment programs. It is also useful for refining multiple alignments obtained by other methods.
3
Arenas-Díaz, Edgar D., Helga Ochoterena, and Katya Rodríguez-Vázquez. "Multiple Sequence Alignment Using a Genetic Algorithm and GLOCSA." Journal of Artificial Evolution and Applications 2009 (August 27, 2009): 1–10. http://dx.doi.org/10.1155/2009/963150.
Full textAbstract:
Algorithms that minimize putative synapomorphy in an alignment cannot be directly implemented since trivial cases with concatenated sequences would be selected because they would imply a minimum number of events to be explained (e.g., a single insertion/deletion would be required to explain divergence among two sequences). Therefore, indirect measures to approach parsimony need to be implemented. In this paper, we thoroughly present a Global Criterion for Sequence Alignment (GLOCSA) that uses a scoring function to globally rate multiple alignments aiming to produce matrices that minimize the number of putative synapomorphies. We also present a Genetic Algorithm that uses GLOCSA as the objective function to produce sequence alignments refining alignments previously generated by additional existing alignment tools (we recommend MUSCLE). We show that in the example cases our GLOCSA-guided Genetic Algorithm (GGGA) does improve the GLOCSA values, resulting in alignments that imply less putative synapomorphies.
4
WANG, ZHUOZHI, and KAIZHONG ZHANG. "MULTIPLE RNA STRUCTURE ALIGNMENT." Journal of Bioinformatics and Computational Biology 03, no. 03 (June 2005): 609–26. http://dx.doi.org/10.1142/s0219720005001296.
Full textAbstract:
Ribonucleic Acid (RNA) structures can be viewed as a special kind of strings where characters in a string can bond with each other. The question of aligning two RNA structures has been studied for a while, and there are several successful algorithms that are based upon different models. In this paper, by adopting the model introduced in Wang and Zhang,19 we propose two algorithms to attack the question of aligning multiple RNA structures. Our methods are to reduce the multiple RNA structure alignment problem to the problem of aligning two RNA structure alignments. Meanwhile, we will show that the framework of sequence center star alignment algorithm can be applied to the problem of multiple RNA structure alignment, and if the triangle inequality is met in the scoring matrix, the approximation ratio of the algorithm remains to be [Formula: see text], where n is the total number of structures.
5
BACKOFEN, ROLF, and SEBASTIAN WILL. "LOCAL SEQUENCE-STRUCTURE MOTIFS IN RNA." Journal of Bioinformatics and Computational Biology 02, no. 04 (December 2004): 681–98. http://dx.doi.org/10.1142/s0219720004000818.
Full textAbstract:
Ribonuclic acid (RNA) enjoys increasing interest in molecular biology; despite this interest fundamental algorithms are lacking, e.g. for identifying local motifs. As proteins, RNA molecules have a distinctive structure. Therefore, in addition to sequence information, structure plays an important part in assessing the similarity of RNAs. Furthermore, common sequence-structure features in two or several RNA molecules are often only spatially local, where possibly large parts of the molecules are dissimilar. Consequently, we address the problem of comparing RNA molecules by computing an optimal local alignment with respect to sequence and structure information. While local alignment is superior to global alignment for identifying local similarities, no general local sequence-structure alignment algorithms are currently known. We suggest a new general definition of locality for sequence-structure alignments that is biologically motivated and efficiently tractable. To show the former, we discuss locality of RNA and prove that the defined locality means connectivity by atomic and non-atomic bonds. To show the latter, we present an efficient algorithm for the newly defined pairwise local sequence-structure alignment (lssa) problem for RNA. For molecules of lengthes n and m, the algorithm has worst-case time complexity of O(n2·m2· max (n,m)) and a space complexity of only O(n·m). An implementation of our algorithm is available at . Its runtime is competitive with global sequence-structure alignment.
6
Mirzaei, Soraya, Jafar Razmara, and Shahriar Lotfi. "GADP-align: A genetic algorithm and dynamic programming-based method for structural alignment of proteins." BioImpacts 11, no. 4 (July 8, 2020): 271–79. http://dx.doi.org/10.34172/bi.2021.37.
Full textAbstract:
Introduction: Similarity analysis of protein structure is considered as a fundamental step to give insight into the relationships between proteins. The primary step in structural alignment is looking for the optimal correspondence between residues of two structures to optimize the scoring function. An exhaustive search for finding such a correspondence between two structures is intractable. Methods: In this paper, a hybrid method is proposed, namely GADP-align, for pairwise protein structure alignment. The proposed method looks for an optimal alignment using a hybrid method based on a genetic algorithm and an iterative dynamic programming technique. To this end, the method first creates an initial map of correspondence between secondary structure elements (SSEs) of two proteins. Then, a genetic algorithm combined with an iterative dynamic programming algorithm is employed to optimize the alignment. Results: The GADP-align algorithm was employed to align 10 ‘difficult to align’ protein pairs in order to evaluate its performance. The experimental study shows that the proposed hybrid method produces highly accurate alignments in comparison with the methods using exactly the dynamic programming technique. Furthermore, the proposed method prevents the local optimal traps caused by the unsuitable initial guess of the corresponding residues. Conclusion: The findings of this paper demonstrate that employing the genetic algorithm along with the dynamic programming technique yields highly accurate alignments between a protein pair by exploring the global alignment and avoiding trapping in local alignments.
7
Zhou, Bin, and Wei Wang. "Fast Compass Alignment Algorithm of FOG SINS under Sway Condition." Applied Mechanics and Materials 321-324 (June 2013): 2171–76. http://dx.doi.org/10.4028/www.scientific.net/amm.321-324.2171.
Full textAbstract:
Through research on initial alignment problem of fiber optic gyro SINS in the sway condition, this paper proposed a rapid compass alignment scheme with variable parameters, which can accomplish rapid initial alignment. Firstly, analysted SINS compass alignment principle, and gave a concrete realization method which has the same calculation procedure with full damping navigation algorithm. This method makes the alignment and navigation to use the same set of algorithms, and can effectively reduce algorithm complexity. Simulation and repeatedly sway test results show that the alignment algorithm is effective. The alignment precision and instrument accuracy is consistent, it can meet the requirements of the initial alignment.
8
Ravi, Sujith, and Kevin Knight. "Does GIZA++ Make Search Errors?" Computational Linguistics 36, no. 3 (September 2010): 295–302. http://dx.doi.org/10.1162/coli_a_00008.
Full textAbstract:
Word alignment is a critical procedure within statistical machine translation (SMT). Brown et al. (1993) have provided the most popular word alignment algorithm to date, one that has been implemented in the GIZA (Al-Onaizan et al., 1999) and GIZA++ (Och and Ney 2003) software and adopted by nearly every SMT project. In this article, we investigate whether this algorithm makes search errors when it computes Viterbi alignments, that is, whether it returns alignments that are sub-optimal according to a trained model.
9
Kuchaiev, Oleksii, Tijana Milenković, Vesna Memišević, Wayne Hayes, and Nataša Pržulj. "Topological network alignment uncovers biological function and phylogeny." Journal of The Royal Society Interface 7, no. 50 (March 24, 2010): 1341–54. http://dx.doi.org/10.1098/rsif.2010.0063.
Full textAbstract:
Sequence comparison and alignment has had an enormous impact on our understanding of evolution, biology and disease. Comparison and alignment of biological networks will probably have a similar impact. Existing network alignments use information external to the networks, such as sequence, because no good algorithm for purely topological alignment has yet been devised. In this paper, we present a novel algorithm based solely on network topology, that can be used to align any two networks. We apply it to biological networks to produce by far the most complete topological alignments of biological networks to date. We demonstrate that both species phylogeny and detailed biological function of individual proteins can be extracted from our alignments. Topology-based alignments have the potential to provide a completely new, independent source of phylogenetic information. Our alignment of the protein–protein interaction networks of two very different species—yeast and human—indicate that even distant species share a surprising amount of network topology, suggesting broad similarities in internal cellular wiring across all life on Earth.
10
Lin, F., Q. Chen, and L. M. Peng. "REW– exit-wave reconstruction and alignments for focus-variation high-resolution transmission electron microscopy images." Journal of Applied Crystallography 40, no. 3 (May 15, 2007): 614. http://dx.doi.org/10.1107/s0021889807008588.
Full textAbstract:
A Windows-based computer program has been developed for exit-wave reconstruction and experimental high-resolution transmission electron microscopy image alignment. While the exit-wave reconstruction is performed mainly using the maximum-likelihood method, image alignments may be carried out using several algorithms, including the time-consuming but robust genetic algorithm.
11
Lin, Weiwei, and Reiko Haga. "Matching Cyber Security Ontologies through Genetic Algorithm-Based Ontology Alignment Technique." Security and Communication Networks 2021 (November 30, 2021): 1–7. http://dx.doi.org/10.1155/2021/4856265.
Full textAbstract:
Security ontology can be used to build a shared knowledge model for an application domain to overcome the data heterogeneity issue, but it suffers from its own heterogeneity issue. Finding identical entities in two ontologies, i.e., ontology alignment, is a solution. It is important to select an effective similarity measure (SM) to distinguish heterogeneous entities. However, due to the complex semantic relationships among concepts, no SM is ensured to be effective in all alignment tasks. The aggregation of SMs so that their advantages and disadvantages complement each other directly affects the quality of alignments. In this work, we formally define this problem, discuss its challenges, and present a problem-specific genetic algorithm (GA) to effectively address it. We experimentally test our approach on bibliographic tracks provided by OAEI and five pairs of security ontologies. The results show that GA can effectively address different heterogeneous ontology-alignment tasks and determine high-quality security ontology alignments.
12
Antunes, Cauã Roca, Alexandre Rademaker, and Mara Abel. "A faster and less aggressive algorithm for correcting conservativity violations in ontology alignments." Applied Ontology 16, no. 3 (July 21, 2021): 277–96. http://dx.doi.org/10.3233/ao-210243.
Full textAbstract:
Ontologies are computational artifacts that model consensual aspects of reality. In distributed contexts, applications often need to utilize information from several distinct ontologies. In order to integrate multiple ontologies, entities modeled in each ontology must be matched through an ontology alignment. However, imperfect alignments may introduce inconsistencies. One kind of inconsistency, which is often introduced, is the violation of the conservativity principle, that states that the alignment should not introduce new subsumption relations between entities from the same source ontology. We propose a two-step quadratic-time algorithm for automatically correcting such violations, and evaluate it against datasets from the Ontology Alignment Evaluation Initiative 2019, comparing the results to a state-of-the-art approach. The proposed algorithm was significantly faster and less aggressive; that is, it performed fewer modifications over the original alignment when compared to the state-of-the-art algorithm.
13
Ji, Yukai, Tao Huang, Chunlai Ma, Chao Hu, Zhanfeng Wang, and Anmin Fu. "IMCSA: Providing Better Sequence Alignment Space for Industrial Control Protocol Reverse Engineering." Security and Communication Networks 2022 (November 24, 2022): 1–9. http://dx.doi.org/10.1155/2022/8026280.
Full textAbstract:
Nowadays, with the wide application of industrial control facilities, industrial control protocol reverse engineering has significant security implications. The reverse method of industrial protocol based on sequence alignment is the current mainstream method because of its high accuracy. However, this method will incur a huge time overhead due to unnecessary alignments during the sequence alignment process. In this paper, we optimize the traditional sequence alignment method by combining the characteristics of industrial control protocols. We improve the frequent sequence mining algorithm, Apriori, to propose a more efficient Bag-of-Words generation algorithm for finding keywords. Then, we precluster the messages based on the generated Bag-of-Words to improve the similarity of the message within a cluster. Finally, we propose an industrial control protocol message preclustering model for sequence alignment, namely, IMCSA. We evaluate it over five industrial control protocols, and the results show that IMCSA can generate clusters with higher message similarity, which will greatly reduce the invalid alignments existing in the sequence alignment stage and ultimately improve the overall efficiency.
14
Cavanaugh, David, and Krishnan Chittur. "A hydrophobic proclivity index for protein alignments." F1000Research 4 (October 21, 2015): 1097. http://dx.doi.org/10.12688/f1000research.6348.1.
Full textAbstract:
Sequence alignment algorithms are fundamental to modern bioinformatics. Sequence alignments are widely used in diverse applications such as phylogenetic analysis, database searches for related sequences to aid identification of unknown protein domain structures and classification of proteins and protein domains. Additionally, alignment algorithms are integral to the location of related proteins to secure understanding of unknown protein functions, to suggest the folded structure of proteins of unknown structure from location of homologous proteins and/or by locating homologous domains of known 3D structure. For proteins, alignment algorithms depend on information about amino acid substitutions that allows for matching sequences that are similar, but not exact. When primary sequence percent identity falls below about 25%, algorithms often fail to identify proteins that may have similar 3D structure. We have created a hydrophobicity scale and a matching dynamic programming algorithm called TMATCH (unpublished report) that is able to match proteins with remote homologs with similar secondary/tertiary structure, even with very low primary sequence matches. In this paper, we describe how we arrived at the hydrophobic scale, how it provides much more information than percent identity matches and some of the implications for better alignments and understanding protein structure.
15
Cavanaugh, David, and Krishnan Chittur. "A hydrophobic proclivity index for protein alignments." F1000Research 4 (October 15, 2020): 1097. http://dx.doi.org/10.12688/f1000research.6348.2.
Full textAbstract:
Sequence alignment algorithms are fundamental to modern bioinformatics. Sequence alignments are widely used in diverse applications such as phylogenetic analysis, database searches for related sequences to aid identification of unknown protein domain structures and classification of proteins and protein domains. Additionally, alignment algorithms are integral to the location of related proteins to secure understanding of unknown protein functions, to suggest the folded structure of proteins of unknown structure from location of homologous proteins and/or by locating homologous domains of known 3D structure. For proteins, alignment algorithms depend on information about amino acid substitutions that allows for matching sequences that are similar, but not exact. When primary sequence percent identity falls below about 25%, algorithms often fail to identify proteins that may have similar 3D structure. We have created a hydrophobicity scale and a matching dynamic programming algorithm called TMATCH (preprint report) that is able to match proteins with remote homologs with similar secondary/tertiary structure, even with very low primary sequence matches. In this paper, we describe how we arrived at the hydrophobic scale, how it provides much more information than percent identity matches and some of the implications for better alignments and understanding protein structure.
16
Chen, Jing, and Jia Huang. "A novel network aligner for the analysis of multiple protein-protein interaction networks." Computer Science and Information Systems, no. 00 (2021): 30. http://dx.doi.org/10.2298/csis200909030c.
Full textAbstract:
The analysis of protein-protein interaction networks can transfer the knowledge of well-studied biological functions to functions that are not yet adequately investigated by constructing networks and extracting similar network structures in different species. Multiple network alignment can be used to find similar regions among multiple networks. In this paper, we introduce Accurate Combined Clustering Multiple Network Alignment (ACCMNA), which is a new and accurate multiple network alignment algorithm. It uses both topology and sequence similarity information. First, the importance of all the nodes is calculated according to the network structures. Second, the seed-and-extend framework is used to conduct an iterative search. In each iteration, a clustering method is combined to generate the alignment. Extensive experimental results show that ACCMNA outperformed the state-of-the-art algorithms in producing functionally consistent and topological conservation alignments within an acceptable running time.
17
Tang, Jun, Hongwei Bian, Heng Ma, and Rongying Wang. "One-Step Initial Alignment Algorithm for SINS in the ECI Frame Based on the Inertial Attitude Measurement of the CNS." Sensors 22, no. 14 (July 8, 2022): 5123. http://dx.doi.org/10.3390/s22145123.
Full textAbstract:
To solve the problem of high-precision and fast initial alignment for the Strapdown Inertial Navigation System (SINS) under both dynamic and static conditions, the high-precision attitude measured by the celestial navigation system (CNS) is used as the reference information for the initial alignment. The alignment algorithm is derived in the Earth-centered inertial (ECI) frame. Compared with the alignment algorithm in the navigation frame, it is independent of position parameters and avoids the influence of the approximate error caused by the dynamic deflection angle. In addition, hull deformation is considered in attitude optimal estimation, which can realize initial the alignment of the SINS installed in various parts of the carrier. On this basis, the velocity measurement information is added to the alignment process, which further improves the accuracy and speed of the initial alignment under static conditions. The experimental results show that the algorithms proposed in this paper have better performance in alignment accuracy, speed, and stability. The attitude and velocity matching algorithm in the ECI frame can achieve alignment accuracy better than 0.6′. The attitude matching algorithm in the ECI frame has better robustness and can be used for both dynamic and static conditions, which can achieve alignment accuracy better than 1.3′.
18
Chauve, Cedric, Julien Courtiel, and Yann Ponty. "Counting, Generating, Analyzing and Sampling Tree Alignments." International Journal of Foundations of Computer Science 29, no. 05 (August 2018): 741–67. http://dx.doi.org/10.1142/s0129054118420030.
Full textAbstract:
Pairwise ordered tree alignment are combinatorial objects that appear in important applications, such as RNA secondary structure comparison. However, the usual representation of tree alignments as supertrees is ambiguous, i.e. two distinct supertrees may induce identical sets of matches between identical pairs of trees. This ambiguity is uninformative, and detrimental to any probabilistic analysis. In this work, we consider tree alignments up to equivalence. Our first result is a precise asymptotic enumeration of tree alignments, obtained from a context-free grammar by mean of basic analytic combinatorics. Our second result focuses on alignments between two given ordered trees [Formula: see text] and [Formula: see text]. By refining our grammar to align specific trees, we obtain a decomposition scheme for the space of alignments, and use it to design an efficient dynamic programming algorithm for sampling alignments under the Gibbs-Boltzmann probability distribution. This generalizes existing tree alignment algorithms, and opens the door for a probabilistic analysis of the space of suboptimal alignments.
19
SALEM, SAEED, MOHAMMED J. ZAKI, and CHRISTOPHER BYSTROFF. "ITERATIVE NON-SEQUENTIAL PROTEIN STRUCTURAL ALIGNMENT." Journal of Bioinformatics and Computational Biology 07, no. 03 (June 2009): 571–96. http://dx.doi.org/10.1142/s0219720009004205.
Full textAbstract:
Structural similarity between proteins gives us insights into their evolutionary relationships when there is low sequence similarity. In this paper, we present a novel approach called SNAP for non-sequential pair-wise structural alignment. Starting from an initial alignment, our approach iterates over a two-step process consisting of a superposition step and an alignment step, until convergence. We propose a novel greedy algorithm to construct both sequential and non-sequential alignments. The quality of SNAP alignments were assessed by comparing against the manually curated reference alignments in the challenging SISY and RIPC datasets. Moreover, when applied to a dataset of 4410 protein pairs selected from the CATH database, SNAP produced longer alignments with lower rmsd than several state-of-the-art alignment methods. Classification of folds using SNAP alignments was both highly sensitive and highly selective. The SNAP software along with the datasets are available online at
20
Liner, Christopher L., and Robert G. Clapp. "Nonlinear pairwise alignment of seismic traces." GEOPHYSICS 69, no. 6 (November 2004): 1552–59. http://dx.doi.org/10.1190/1.1836828.
Full textAbstract:
Seismic trace alignment is a recurring need in seismic processing and interpretation. For global alignment via static shift, there are robust tools available, including crosscorrelation. However, another kind of alignment problem arises in applications as diverse as associating synthetic seismograms to field data, harmonizing P‐ and S‐wave data, residual NMO, and final multilevel flattening of common image gathers. These cases require combinations of trace compression, extension, and shift—all of which are time variant. The difficulty is to find a mapping between the traces that is in some senseoptimum. This problem is solved here using a modified form of the Needleman‐Wunsch algorithm, a global optimization method originally developed for aligning amino acid sequences in proteins. Applied to seismic traces, this algorithm provides a nonlinear mapping of one seismic trace onto another. The method extends to multitrace alignment since that problem can be broken down into a cascade of pairwise alignments. Seismic implementation of the Needleman‐Wunsch algorithm is a promising new tool for nonlinear alignment and flattening of seismic data.
21
Milano, Marianna, Pietro Hiram Guzzi, and Mario Cannataro. "Design and Implementation of New Local Alignment Algorithm for Multilayer Networks." Entropy 24, no. 9 (September 9, 2022): 1272. http://dx.doi.org/10.3390/e24091272.
Full textAbstract:
Network alignment (NA) is a popular research field that aims to develop algorithms for comparing networks. Applications of network alignment span many fields, from biology to social network analysis. NA comes in two forms: global network alignment (GNA), which aims to find a global similarity, and LNA, which aims to find local regions of similarity. Recently, there has been an increasing interest in introducing complex network models such as multilayer networks. Multilayer networks are common in many application scenarios, such as modelling of relations among people in a social network or representing the interplay of different molecules in a cell or different cells in the brain. Consequently, the need to introduce algorithms for the comparison of such multilayer networks, i.e., local network alignment, arises. Existing algorithms for LNA do not perform well on multilayer networks since they cannot consider inter-layer edges. Thus, we propose local alignment of multilayer networks (MultiLoAl), a novel algorithm for the local alignment of multilayer networks. We define the local alignment of multilayer networks and propose a heuristic for solving it. We present an extensive assessment indicating the strength of the algorithm. Furthermore, we implemented a synthetic multilayer network generator to build the data for the algorithm’s evaluation.
22
Rautiainen, Mikko, Veli Mäkinen, and Tobias Marschall. "Bit-parallel sequence-to-graph alignment." Bioinformatics 35, no. 19 (March 9, 2019): 3599–607. http://dx.doi.org/10.1093/bioinformatics/btz162.
Full textAbstract:
Abstract Motivation Graphs are commonly used to represent sets of sequences. Either edges or nodes can be labeled by sequences, so that each path in the graph spells a concatenated sequence. Examples include graphs to represent genome assemblies, such as string graphs and de Bruijn graphs, and graphs to represent a pan-genome and hence the genetic variation present in a population. Being able to align sequencing reads to such graphs is a key step for many analyses and its applications include genome assembly, read error correction and variant calling with respect to a variation graph. Results We generalize two linear sequence-to-sequence algorithms to graphs: the Shift-And algorithm for exact matching and Myers’ bitvector algorithm for semi-global alignment. These linear algorithms are both based on processing w sequence characters with a constant number of operations, where w is the word size of the machine (commonly 64), and achieve a speedup of up to w over naive algorithms. For a graph with |V| nodes and |E| edges and a sequence of length m, our bitvector-based graph alignment algorithm reaches a worst case runtime of O(|V|+⌈mw⌉|E| log w) for acyclic graphs and O(|V|+m|E| log w) for arbitrary cyclic graphs. We apply it to five different types of graphs and observe a speedup between 3-fold and 20-fold compared with a previous (asymptotically optimal) alignment algorithm. Availability and implementation https://github.com/maickrau/GraphAligner Supplementary information Supplementary data are available at Bioinformatics online.
23
Demin, A. V. "Alignment algorithm for composite mirrors." Computer Optics 41, no. 2 (2017): 291–94. http://dx.doi.org/10.18287/2412-6179-2017-41-2-291-294.
Full text
24
Huang, X., and K. M. Chao. "A generalized global alignment algorithm." Bioinformatics 19, no. 2 (January 22, 2003): 228–33. http://dx.doi.org/10.1093/bioinformatics/19.2.228.
Full text
25
Nelson, Reed, Rosa Aghdam, and Claudia Solis-Lemus. "MiNAA: Microbiome Network Alignment Algorithm." Journal of Open Source Software 9, no. 96 (April 7, 2024): 5448. http://dx.doi.org/10.21105/joss.05448.
Full text
26
Tang, Chuan Yi, Chin Lung Lu, Margaret Dah-Tsyr Chang, Yin-Te Tsai, Yuh-Ju Sun, Kun-Mao Chao, Jia-Ming Chang, et al. "Constrained Multiple Sequence Alignment Tool Development and Its Application to RNase Family Alignment." Journal of Bioinformatics and Computational Biology 01, no. 02 (July 2003): 267–87. http://dx.doi.org/10.1142/s0219720003000095.
Full textAbstract:
In this paper, we design a heuristic algorithm of computing a constrained multiple sequence alignment (CMSA for short) for guaranteeing that the generated alignment satisfies the user-specified constraints that some particular residues should be aligned together. If the number of residues needed to be aligned together is a constant α, then the time-complexity of our CMSA algorithm for aligning K sequences is O(αKn4), where n is the maximum of the lengths of sequences. In addition, we have built up such a CMSA software system and made several experiments on the RNase sequences, which mainly function in catalyzing the degradation of RNA molecules. The resulting alignments illustrate the practicability of our method.
27
Jeong, Sang Hwa, Gwang Ho Kim, and Kyoung Rae Cha. "A Study on Automation Program for the Characteristics Improvement of Optical Element Alignment System." Key Engineering Materials 326-328 (December 2006): 305–8. http://dx.doi.org/10.4028/www.scientific.net/kem.326-328.305.
Full textAbstract:
With the increasing demand for VBNS and VDSL, the development of the kernel parts of optical communication such as PLC(Planar Light Circuit), Coupler, and WDM elements has increased. The optical transmitter and the receiver module need precise and mechanical alignment within a few micrometers to couple the semiconductor device, optical fiber and waveguide. The alignment and the attachment technology are very important in the fabrication of an optical element. Presently, the alignment of the optical element is time consuming, and an effective alignment algorithm has not yet to be developed. In this paper, the optical element alignment of the multi-axis ultra precision stage is studied. Two alignment algorithms applied to the ultra precision multi-axis stage are used, the field search algorithm and the peak search algorithm. The automation program to improve the characteristics of the optical element alignment system is developed by Labview programming and is composed of three tabs, the field search tab, plotting tab and peak search tab. The developed program is applied to an actual system to determine the improvement in alignment performance.
28
Kang, Li, Lingyun Ye, and Kaichen Song. "A Fast in-Motion Alignment Algorithm for DVL Aided SINS." Mathematical Problems in Engineering 2014 (2014): 1–12. http://dx.doi.org/10.1155/2014/593692.
Full textAbstract:
Doppler velocity log (DVL) aided strapdown inertial navigation system (SINS) is a common navigation method for underwater applications. Owing to the in-motion condition and the lack of the GPS, it is a challenge to align a SINS under water. This paper proposed a complete in-motion alignment solution for both attitude and position. The velocity update equation and its integral form in the body frame are studied, and the attitude coarse alignment becomes an optimization-based attitude determination problem between the body frame velocity and the integral form of gravity. The body frame velocity and the Earth frame position are separately treated, and the position alignment problem turns into an equation solving problem. Simulation and on-lake tests are carried out to examine the algorithm. The heading could reach around 10 deg accuracy and the pitch and roll could be aligned up to 0.05 deg in 60 s. With attitude error of this level, the heading could reach 1 deg accuracy in 240 s using unscented Kalman filter (UKF) based fine alignment. The final position error could achieve 1.5% of the voyage distance. This scheme can also be applied to other body frame velocity aided SINS alignments.
29
Long, Hai Xia, Li Hua Wu, and Yu Zhang. "Multiple Sequence Alignment Based on Profile Hidden Markov Model and Quantum-Behaved Particle Swarm Optimization with Selection Method." Advanced Materials Research 282-283 (July 2011): 7–12. http://dx.doi.org/10.4028/www.scientific.net/amr.282-283.7.
Full textAbstract:
Multiple sequence alignment (MSA) is an NP-complete and important problem in bioinformatics. Currently, profile hidden Markov model (HMM) is widely used for multiple sequence alignment. In this paper, Quantum-behaved Particle Swarm Optimization with selection operation (SQPSO) is presented, which is used to train profile HMM. Furthermore, an integration algorithm based on the profile HMM and SQPSO for the MSA is constructed. The approach is examined by using multiple nucleotides and protein sequences and compared with other algorithms. The results of the comparisons show that the HMM trained with SQPSO and QPSO yield better alignments than other most commonly used HMM training methods such as Baum–Welch and PSO.
30
Jiang, Yihang, Yuankai Qi, Will Ke Wang, Brinnae Bent, Robert Avram, Jeffrey Olgin, and Jessilyn Dunn. "EventDTW: An Improved Dynamic Time Warping Algorithm for Aligning Biomedical Signals of Nonuniform Sampling Frequencies." Sensors 20, no. 9 (May 9, 2020): 2700. http://dx.doi.org/10.3390/s20092700.
Full textAbstract:
The dynamic time warping (DTW) algorithm is widely used in pattern matching and sequence alignment tasks, including speech recognition and time series clustering. However, DTW algorithms perform poorly when aligning sequences of uneven sampling frequencies. This makes it difficult to apply DTW to practical problems, such as aligning signals that are recorded simultaneously by sensors with different, uneven, and dynamic sampling frequencies. As multi-modal sensing technologies become increasingly popular, it is necessary to develop methods for high quality alignment of such signals. Here we propose a DTW algorithm called EventDTW which uses information propagated from defined events as basis for path matching and hence sequence alignment. We have developed two metrics, the error rate (ER) and the singularity score (SS), to define and evaluate alignment quality and to enable comparison of performance across DTW algorithms. We demonstrate the utility of these metrics on 84 publicly-available signals in addition to our own multi-modal biomedical signals. EventDTW outperformed existing DTW algorithms for optimal alignment of signals with different sampling frequencies in 37% of artificial signal alignment tasks and 76% of real-world signal alignment tasks.
31
Yan, Zheping, Lu Wang, Tongda Wang, Honghan Zhang, and Zewen Yang. "Polar Transversal Initial Alignment Algorithm for UUV with a Large Misalignment Angle." Sensors 18, no. 10 (September 25, 2018): 3231. http://dx.doi.org/10.3390/s18103231.
Full textAbstract:
The conventional initial alignment algorithms are invalid in the polar region. This is caused by the rapid convergence of the Earth meridians in the high-latitude areas. However, the initial alignment algorithms are important for the accurate navigation of Unmanned Underwater Vehicles. The polar transversal initial alignment algorithm is proposed to overcome this problem. In the polar transversal initial alignment algorithm, the transversal geographic frame is chosen as the navigation frame. The polar region in the conventional frames is equivalent to the equatorial region in the transversal frames. Therefore, the polar transversal initial can be effectively applied in the polar region. According to the complex environment in the polar region, a large misalignment angle is considered in this paper. Based on the large misalignment angle condition, the non-linear dynamics models are established. In addition, the simplified unscented Kalman filter (UKF) is chosen to realize the data fusion. Two comparison simulations and an experiment are performed to verify the performance of the proposed algorithm. The simulation and experiment results indicate the validity of the proposed algorithm, especially when large misalignment angles occur.
32
Lebsir, Rabah, Abdesslem Layeb, and Tahi Fariza. "A Greedy Clustering Algorithm for Multiple Sequence Alignment." International Journal of Cognitive Informatics and Natural Intelligence 15, no. 4 (October 2021): 1–17. http://dx.doi.org/10.4018/ijcini.20211001.oa41.
Full textAbstract:
This paper presents a strategy to tackle the Multiple Sequence Alignment (MSA) problem, which is one of the most important tasks in the biological sequence analysis. Its role is to align the sequences in their entirety to derive relationships and common characteristics between a set of protein or nucleotide sequences. The MSA problem was proved to be an NP-Hard problem. The proposed strategy incorporates a new idea based on the well-known divide and conquer paradigm. This paper presents a novel method of clustering sequences as a preliminary step to improve the final alignment; this decomposition can be used as an optimization procedure with any MSA aligner to explore promising alignments of the search space. In their solution, authors proposed to align the clusters in a parallel and distributed way in order to benefit from parallel architectures. The strategy was tested using classical benchmarks like BAliBASE, Sabre, Prefab4 and Oxm, and the experimental results show that it gives good results by comparing to the other aligners.
33
Wilburn, Grey W., and Sean R. Eddy. "Remote homology search with hidden Potts models." PLOS Computational Biology 16, no. 11 (November 30, 2020): e1008085. http://dx.doi.org/10.1371/journal.pcbi.1008085.
Full textAbstract:
Most methods for biological sequence homology search and alignment work with primary sequence alone, neglecting higher-order correlations. Recently, statistical physics models called Potts models have been used to infer all-by-all pairwise correlations between sites in deep multiple sequence alignments, and these pairwise couplings have improved 3D structure predictions. Here we extend the use of Potts models from structure prediction to sequence alignment and homology search by developing what we call a hidden Potts model (HPM) that merges a Potts emission process to a generative probability model of insertion and deletion. Because an HPM is incompatible with efficient dynamic programming alignment algorithms, we develop an approximate algorithm based on importance sampling, using simpler probabilistic models as proposal distributions. We test an HPM implementation on RNA structure homology search benchmarks, where we can compare directly to exact alignment methods that capture nested RNA base-pairing correlations (stochastic context-free grammars). HPMs perform promisingly in these proof of principle experiments.
34
AY, FERHAT, TAMER KAHVECI, and VALÉRIE DE CRÉCY-LAGARD. "A FAST AND ACCURATE ALGORITHM FOR COMPARATIVE ANALYSIS OF METABOLIC PATHWAYS." Journal of Bioinformatics and Computational Biology 07, no. 03 (June 2009): 389–428. http://dx.doi.org/10.1142/s0219720009004163.
Full textAbstract:
Pathways show how different biochemical entities interact with one another to perform vital functions for the survival of an organism. Comparative analysis of pathways is crucial in identifying functional similarities that are difficult to identify by comparing individual entities that build up these pathways. When interacting entities are of single type, the problem of identifying similarities by aligning the pathways can be reduced to graph isomorphism problem. For pathways with varying types of entities such as metabolic pathways, alignment problem is even more challenging. In order to simplify this problem, existing methods often reduce metabolic pathways to graphs with restricted topologies and single type of nodes. However, these abstractions reduce the relevance of the alignment significantly as they cause losses in the information content. In this paper, we describe an algorithm to solve the pairwise alignment problem for metabolic pathways. A distinguishing feature of our method is that it aligns different types of entities, such as enzymes, reactions and compounds. Also, our approach is free of any abstraction in modeling the pathways. We pursue the intuition that both pairwise similarities of entities (homology) and the organization of their interactions (topology) are important for metabolic pathway alignment. In our algorithm, we account for both by creating an eigenvalue problem for each entity type. We enforce the consistency while combining the alignments of different entity types by considering the reachability sets of entities. Our experiments show that our method finds biologically and statistically significant alignments in the order of milliseconds. Availability: Our software and the source code in C programming language is available at .
35
Xue, Xingsi, and Jianhua Liu. "Optimizing Ontology Alignment Through Compact MOEA/D." International Journal of Pattern Recognition and Artificial Intelligence 31, no. 04 (February 2, 2017): 1759004. http://dx.doi.org/10.1142/s0218001417590042.
Full textAbstract:
In order to support semantic inter-operability in many domains through disparate ontologies, we need to identify correspondences between the entities across different ontologies, which is commonly known as ontology matching. One of the challenges in ontology matching domain is how to select weights and thresholds in the ontology aligning process to aggregate the various similarity measures to obtain a satisfactory alignment, so called ontology meta-matching problem. Nowadays, the most suitable methodology to address the ontology meta-matching problem is through Evolutionary Algorithm (EA), and the Multi-Objective Evolutionary Algorithms (MOEA) based approaches are emerging as a new efficient methodology to face the meta-matching problem. Moreover, for dynamic applications, it is necessary to perform the system self-tuning process at runtime, and thus, efficiency of the configuration search strategies becomes critical. To this end, in this paper, we propose a problem-specific compact Multi-Objective Evolutionary Algorithm based on Decomposition (MOEA/D), in the whole ontology matching process of ontology meta-matching system, to optimize the ontology alignment. The experimental results show that our proposal is able to highly reduce the execution time and main memory consumption of determining the optimal alignments through MOEA/D based approach by 58.96% and 67.60% on average, respectively, and the quality of the alignments obtained is better than the state of the art ontology matching systems.
36
NARIMANI, ZAHRA, HAMID BEIGY, and HASSAN ABOLHASSANI. "A NEW GENETIC ALGORITHM FOR MULTIPLE SEQUENCE ALIGNMENT." International Journal of Computational Intelligence and Applications 11, no. 04 (December 2012): 1250023. http://dx.doi.org/10.1142/s146902681250023x.
Full textAbstract:
Multiple sequence alignment (MSA) is one of the basic and important problems in molecular biology. MSA can be used for different purposes including finding the conserved motifs and structurally important regions in protein sequences and determine evolutionary distance between sequences. Aligning several sequences cannot be done in polynomial time and therefore heuristic methods such as genetic algorithms can be used to find approximate solutions of MSA problems. Several algorithms based on genetic algorithms have been developed for this problem in recent years. Most of these algorithms use very complicated, problem specific and time consuming mutation operators. In this paper, we propose a new algorithm that uses a new way of population initialization and simple mutation and recombination operators. The strength of the proposed GA is using simple mutation operators and also a special recombination operator that does not have problems of similar recombination operators in other GAs. The experimental results show that the proposed algorithm is capable of finding good MSAs in contrast to existing methods, while it uses simple operators with low computational complexity.
37
Lee, Seyoung, Jiye Lee, and Jehee Lee. "Learning Virtual Chimeras by Dynamic Motion Reassembly." ACM Transactions on Graphics 41, no. 6 (November 30, 2022): 1–13. http://dx.doi.org/10.1145/3550454.3555489.
Full textAbstract:
The Chimera is a mythological hybrid creature composed of different animal parts. The chimera's movements are highly dependent on the spatial and temporal alignments of its composing parts. In this paper, we present a novel algorithm that creates and animates chimeras by dynamically reassembling source characters and their movements. Our algorithm exploits a two-network architecture: part assembler and dynamic controller. The part assembler is a supervised learning layer that searches for the spatial alignment among body parts, assuming that the temporal alignment is provided. The dynamic controller is a reinforcement learning layer that learns robust control policy for a wide variety of potential temporal alignments. These two layers are tightly intertwined and learned simultaneously. The chimera animation generated by our algorithm is energy efficient and expressive in terms of describing weight shifting, balancing, and full-body coordination. We demonstrate the versatility of our algorithm by generating the motor skills of a large variety of chimeras from limited source characters.
38
Och, Franz Josef, and Hermann Ney. "A Systematic Comparison of Various Statistical Alignment Models." Computational Linguistics 29, no. 1 (March 2003): 19–51. http://dx.doi.org/10.1162/089120103321337421.
Full textAbstract:
We present and compare various methods for computing word alignments using statistical or heuristic models. We consider the five alignment models presented in Brown, Della Pietra, Della Pietra, and Mercer (1993), the hidden Markov alignment model, smoothing techniques, and refinements. These statistical models are compared with two heuristic models based on the Dice coefficient. We present different methods for combining word alignments to perform a symmetrization of directed statistical alignment models. As evaluation criterion, we use the quality of the resulting Viterbi alignment compared to a manually produced reference alignment. We evaluate the models on the German-English Verbmobil task and the French-English Hansards task. We perform a detailed analysis of various design decisions of our statistical alignment system and evaluate these on training corpora of various sizes. An important result is that refined alignment models with a first-order dependence and a fertility model yield significantly better results than simple heuristic models. In the Appendix, we present an efficient training algorithm for the alignment models presented.
39
Kamionskaya, A. M., and M. A. Korotkova. "Multiple Alignment of Promoter Sequences from the Human Genome." Biotekhnologiya 36, no. 4 (2020): 7–14. http://dx.doi.org/10.21519/0234-2758-2020-36-4-7-14.
Full textAbstract:
A new algorithm for multiple alignment of nucleotide sequences of MAHDS has been developed. A statistically significant multiple alignment of promoter sequences from the human genome was first created using this algorithm. Based on the constructed alignments, 25 classes of promoter sequences were created with the volume of each class exceeding 100 sequences. The classes of promoters can be used to search for promoter sequences in eukaryotic genomes. promoter, class, dynamic programming, human genome. The work was partially supported by the Russian Foundation for Basic Research (Grant no. 20-016-00057).
40
Xue, Xingsi, Xiaojing Wu, and Junfeng Chen. "Optimizing Ontology Alignment Through an Interactive Compact Genetic Algorithm." ACM Transactions on Management Information Systems 12, no. 2 (June 2021): 1–17. http://dx.doi.org/10.1145/3439772.
Full textAbstract:
Ontology provides a shared vocabulary of a domain by formally representing the meaning of its concepts, the properties they possess, and the relations among them, which is the state-of-the-art knowledge modeling technique. However, the ontologies in the same domain could differ in conceptual modeling and granularity level, which yields the ontology heterogeneity problem. To enable data and knowledge transfer, share, and reuse between two intelligent systems, it is important to bridge the semantic gap between the ontologies through the ontology matching technique. To optimize the ontology alignment’s quality, this article proposes an Interactive Compact Genetic Algorithm (ICGA)-based ontology matching technique, which consists of an automatic ontology matching process based on a Compact Genetic Algorithm (CGA) and a collaborative user validating process based on an argumentation framework. First, CGA is used to automatically match the ontologies, and when it gets stuck in the local optima, the collaborative validation based on the multi-relationship argumentation framework is activated to help CGA jump out of the local optima. In addition, we construct a discrete optimization model to define the ontology matching problem and propose a hybrid similarity measure to calculate two concepts’ similarity value. In the experiment, we test the performance of ICGA with the Ontology Alignment Evaluation Initiative’s interactive track, and the experimental results show that ICGA can effectively determine the ontology alignments with high quality.
41
FUTAMURA, NATSUHIKO, SRINIVAS ALURU, and XIAOQIU HUANG. "PARALLEL SYNTENIC ALIGNMENTS." Parallel Processing Letters 13, no. 04 (December 2003): 689–703. http://dx.doi.org/10.1142/s0129626403001604.
Full textAbstract:
Given two genomic DNA sequences, the syntenic alignment problem is to compute an ordered list of subsequences for each sequence such that the corresponding subsequence pairs exhibit a high degree of similarity. Syntenic alignments are useful in comparing genomic DNA from related species and in identifying conserved genes. In this paper, we present a parallel algorithm for computing syntenic alignments that runs in [Formula: see text] time, where m and n are the respective lengths of the two genomic sequences, and p is the number of processors used. Our algorithm is time optimal with respect to the corresponding sequential algorithm and can use [Formula: see text] processors, where n is the length of the larger sequence. The space requirement of the algorithm is [Formula: see text] per processor. Using an implementation of this parallel algorithm, we report the alignment of a gene-rich region of human chromosome 12, namely 12p13 and its syntenic region in mouse chromosome 6 (both over 220,000 base pairs in length) in under 24 minutes on a 64-processor IBM xSeries cluster.
42
Shegay, Maksim V., Vytas K. Švedas, Vladimir V. Voevodin, Dmitry A. Suplatov, and Nina N. Popova. "Guide tree optimization with genetic algorithm to improve multiple protein 3D-structure alignment." Bioinformatics 38, no. 4 (November 26, 2021): 985–89. http://dx.doi.org/10.1093/bioinformatics/btab798.
Full textAbstract:
Abstract Motivation With the increasing availability of 3D-data, the focus of comparative bioinformatic analysis is shifting from protein sequence alignments toward more content-rich 3D-alignments. This raises the need for new ways to improve the accuracy of 3D-superimposition. Results We proposed guide tree optimization with genetic algorithm (GA) as a universal tool to improve the alignment quality of multiple protein 3D-structures systematically. As a proof of concept, we implemented the suggested GA-based approach in popular Matt and Caretta multiple protein 3D-structure alignment (M3DSA) algorithms, leading to a statistically significant improvement of the TM-score quality indicator by up to 220–1523% on ‘SABmark Superfamilies’ (in 49–77% of cases) and ‘SABmark Twilight’ (in 59–80% of cases) datasets. The observed improvement in collections of distant homologies highlights the potentials of GA to optimize 3D-alignments of diverse protein superfamilies as one plausible tool to study the structure–function relationship. Availability and implementation The source codes of patched gaCaretta and gaMatt programs are available open-access at https://github.com/n-canter/gamaps. Supplementary information Supplementary data are available at Bioinformatics online.
43
Huang, Yikun, Xingsi Xue, and Chao Jiang. "Optimizing Ontology Alignment through Improved NSGA-II." Discrete Dynamics in Nature and Society 2020 (June 19, 2020): 1–8. http://dx.doi.org/10.1155/2020/8586058.
Full textAbstract:
Over the past decades, a large number of complex optimization problems have been widely addressed through multiobjective evolutionary algorithms (MOEAs), and the knee solutions of the Pareto front (PF) are most likely to be fitting for the decision maker (DM) without any user preferences. This work investigates the ontology matching problem, which is a challenge in the semantic web (SW) domain. Due to the complex heterogeneity between two different ontologies, it is arduous to get an excellent alignment that meets all DMs’ demands. To this end, a popular MOEA, i.e., nondominated sorting genetic algorithm (NSGA-II), is investigated to address the ontology matching problem, which outputs the knee solutions in the PF to meet diverse DMs’ requirements. In this study, for further enhancing the performance of NSGA-II, we propose to incorporate into NSGA-II’s evolutionary process the monkey king evolution algorithm (MKE) as the local search algorithm. The improved NSGA-II (iNSGA-II) is able to better converge to the real Pareto optimum region and ameliorate the quality of the solution. The experiment uses the famous benchmark given by the ontology alignment evaluation initiative (OAEI) to assess the performance of iNSGA-II, and the experiment results present that iNSGA-II is able to seek out preferable alignments than OAEI’s participators and NSGA-II-based ontology matching technique.
44
Naznin, Farhana, Ruhul Sarker, and Daryl Essam. "Progressive Alignment Method Using Genetic Algorithm for Multiple Sequence Alignment." IEEE Transactions on Evolutionary Computation 16, no. 5 (October 2012): 615–31. http://dx.doi.org/10.1109/tevc.2011.2162849.
Full text
45
Ji, Guo Li, Long Teng Chen, and Liang Liang Chen. "Two-Level Parallel Alignment Based on Sequence Parallel Vectorization." Applied Mechanics and Materials 490-491 (January 2014): 757–62. http://dx.doi.org/10.4028/www.scientific.net/amm.490-491.757.
Full textAbstract:
This paper proposed a way of two-level parallel alignment based on sequence parallel vectorization with GPU acceleration on the Fermi architecture, which integrates sequence parallel vectorization, parallel k-means clustering approximate alignment and parallel Smith-Waterman algorithm. The method converts sequence alignment into vector alignment by first. Then it uses k-means alignment to divide sequences into several groups and reduce the size of sequence data. The expected accurate alignment result is achieved using parallel Smith-Waterman algorithm. The high-throughput mouse T-cell receptor (TCR) sequences were used to validate the proposed method. Under the same hardware condition, comparing to serial Smith-Waterman algorithm and CUDASW++2.0 algorithm, our method is the most efficient alignment algorithm with high alignment accuracy.
46
Schroedl, S. "An Improved Search Algorithm for Optimal Multiple-Sequence Alignment." Journal of Artificial Intelligence Research 23 (May 1, 2005): 587–623. http://dx.doi.org/10.1613/jair.1534.
Full textAbstract:
Multiple sequence alignment (MSA) is a ubiquitous problem in computational biology. Although it is NP-hard to find an optimal solution for an arbitrary number of sequences, due to the importance of this problem researchers are trying to push the limits of exact algorithms further. Since MSA can be cast as a classical path finding problem, it is attracting a growing number of AI researchers interested in heuristic search algorithms as a challenge with actual practical relevance. In this paper, we first review two previous, complementary lines of research. Based on Hirschberg's algorithm, Dynamic Programming needs O(kN^(k-1)) space to store both the search frontier and the nodes needed to reconstruct the solution path, for k sequences of length N. Best first search, on the other hand, has the advantage of bounding the search space that has to be explored using a heuristic. However, it is necessary to maintain all explored nodes up to the final solution in order to prevent the search from re-expanding them at higher cost. Earlier approaches to reduce the Closed list are either incompatible with pruning methods for the Open list, or must retain at least the boundary of the Closed list. In this article, we present an algorithm that attempts at combining the respective advantages; like A* it uses a heuristic for pruning the search space, but reduces both the maximum Open and Closed size to O(kN^(k-1)), as in Dynamic Programming. The underlying idea is to conduct a series of searches with successively increasing upper bounds, but using the DP ordering as the key for the Open priority queue. With a suitable choice of thresholds, in practice, a running time below four times that of A* can be expected. In our experiments we show that our algorithm outperforms one of the currently most successful algorithms for optimal multiple sequence alignments, Partial Expansion A*, both in time and memory. Moreover, we apply a refined heuristic based on optimal alignments not only of pairs of sequences, but of larger subsets. This idea is not new; however, to make it practically relevant we show that it is equally important to bound the heuristic computation appropriately, or the overhead can obliterate any possible gain. Furthermore, we discuss a number of improvements in time and space efficiency with regard to practical implementations. Our algorithm, used in conjunction with higher-dimensional heuristics, is able to calculate for the first time the optimal alignment for almost all of the problems in Reference 1 of the benchmark database BAliBASE.
47
Kim, Hyungjong. "Wafer Center Alignment System of Transfer Robot Based on Reduced Number of Sensors." Sensors 22, no. 21 (November 5, 2022): 8521. http://dx.doi.org/10.3390/s22218521.
Full textAbstract:
This brief presents a wafer alignment algorithm with reduced sensor number that obtains the relative distance of the wafer center and the robot hand. By ‘reduced number’, in spite of smaller number of sensors than the conventional method, we mean an improved method which achieves the similar results to pre-existing algorithms. Indeed, it can be designed with only three sensor data, less than four sensors of the conventional algorithm. Thus, some advantages of the proposed alignment algorithm include that it can be designed with low cost and less computing power. The proposed alignment algorithm is applied to a transfer robot for coater/developer system in semiconductor processing for verifying the performance of the method. The performance of the proposed method is validated by both simulation and experimental results.
48
ABOUELHODA, MOHAMED I., ROBERT GIEGERICH, BEHSHAD BEHZADI, and JEAN-MARC STEYAERT. "ALIGNMENT OF MINISATELLITE MAPS BASED ON RUN-LENGTH ENCODING SCHEME." Journal of Bioinformatics and Computational Biology 07, no. 02 (April 2009): 287–308. http://dx.doi.org/10.1142/s0219720009004060.
Full textAbstract:
Subsequent duplication events are responsible for the evolution of the minisatellite maps. Alignment of two minisatellite maps should therefore take these duplication events into account, in addition to the well-known edit operations. All algorithms for computing an optimal alignment of two maps, including the one presented here, first deduce the costs of optimal duplication scenarios for all substrings of the given maps. Then, they incorporate the pre-computed costs in the alignment recurrence. However, all previous algorithms addressing this problem are dependent on the number of distinct map units (map alphabet) and do not fully make use of the repetitiveness of the map units. In this paper, we present an algorithm that remedies these shortcomings: our algorithm is alphabet-independent and is based on the run-length encoding scheme. It is the fastest in theory, and in practice as well, as shown by experimental results. Furthermore, our alignment model is more general than that of the previous algorithms, and captures better the duplication mechanism. Using our algorithm, we derive a quantitative evidence that there is a directional bias in the growth of minisatellites of the MSY1 dataset.
49
PATEL, VANDANABEN, JASON T. L. WANG, SHEFALI SETIA, ANURAG VERMA, CHARLES D. WARDEN, and KAIZHONG ZHANG. "ON COMPARING TWO STRUCTURED RNA MULTIPLE ALIGNMENTS." Journal of Bioinformatics and Computational Biology 08, no. 06 (December 2010): 967–80. http://dx.doi.org/10.1142/s021972001000504x.
Full textAbstract:
We present a method, called BlockMatch, for aligning two blocks, where a block is an RNA multiple sequence alignment with the consensus secondary structure of the alignment in Stockholm format. The method employs a quadratic-time dynamic programming algorithm for aligning columns and column pairs of the multiple alignments in the blocks. Unlike many other tools that can perform pairwise alignment of either single sequences or structures only, BlockMatch takes into account the characteristics of all the sequences in the blocks along with their consensus structures during the alignment process, thus being able to achieve a high-quality alignment result. We apply BlockMatch to phylogeny reconstruction on a set of 5S rRNA sequences taken from fifteen bacteria species. Experimental results showed that the phylogenetic tree generated by our method is more accurate than the tree constructed based on the widely used ClustalW tool. The BlockMatch algorithm is implemented into a web server, accessible at . A jar file of the program is also available for download from the web server.
50
Li, Hanzhou, Quan Pan, Xiaoxu Wang, Xiangjun Jiang, and Lin Deng. "Kalman Filter Design for Initial Precision Alignment of a Strapdown Inertial Navigation System on a Rocking Base." Journal of Navigation 68, no. 1 (September 18, 2014): 184–95. http://dx.doi.org/10.1017/s0373463314000575.
Full textAbstract:
In this paper, a conventional Strapdown Inertial Navigation System (SINS) alignment method on a disturbed base is analysed. A novel method with an attitude tracking idea is proposed for the rocking base alignment. It is considered in this method that the alignment algorithm should track the rocking base attitude real changes in the alignment process, but not excessively restrain disturbance. According to this idea, a rapid alignment algorithm is devised for the rocking base. In the algorithm, coarse alignment is carried out within 30 s in the inertial frame with alignment precision less than 2°, which meets Kalman filter linearization conditions well. Then a Kalman filter with ten state vectors and four measurement vectors is applied for the fine alignment to improve the capability of the algorithm in tracking the vehicle attitude. A turntable rotation experiment is carried out to validate the capability of the fine algorithm in tracing the large magnitude change during alignment. It is shown that the repeated alignment precision is about 0·04° by the alignment experiment on a rocking vehicle, with alignment time of 180 s. The Laser Strapdown Inertial Navigation System (LINS) ground navigation experiment suggests that the algorithm proposed by this paper can be satisfied without the need of high precision SINS alignment.