Refining the progressive multiple sequence alignment score using genetic algorithms

Date

2006-01-01

Author

Ergezer, Halit
Leblebicioğlu, Mehmet Kemal

Metadata

Show full item record

This work is licensed under a Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 International License.

Item Usage Stats

25
views

0
downloads

Given a set of N (N > 2) sequences, the Multiple Sequence Alignment (MSA) problem is to align these N sequences, possibly with gaps, that bring out the best score due to a given scoring criterion between characters. Multiple sequence alignment is one of the basic tools for interpreting the information obtained from bioinformatics studies. Dynamic Programming (DP) gives the optimal alignment of the two sequences for the given scoring scheme. But, in the case of multiple sequence alignment it requires enormous time and space to obtain the optimal alignment. The time and space requirement increases exponentially with the number of sequences. There are two basic classes of solutions except the DP method: progressive methods and iterative methods. In this study, we try to refine the alignment score obtained by using the progressive method due to given scoring criterion by using an iterative method. As an iterative method genetic algorithm (GA) has been used. The sum-of-pairs (SP) scoring system is used as our target of optimization. There are fifteen operators defined to refine the alignment quality by combining and mutating the alignments in the alignment population. The results show that the novel operators, sliding-window, local-alignment, which have not been used up to now, increase the score of the progressive alignment by amount of % 2.

Subject Keywords

Dynamic program, Iterative method, Multiple sequence alignment, Pairwise alignment, Alignment score

URI

https://hdl.handle.net/11511/55007

Journal

ARTIFICIAL INTELLIGENCE AND NEURAL NETWORKS

Collections

Department of Electrical and Electronics Engineering, Article

Suggestions

OpenMETU
Core

Harnessing molecular excited states with Lanczos chains Baroni, Stefano; Gebauer, Ralph; Malcıoğlu, Osman Barış; Saad, Yousef; Umari, Paolo; Xian, Jiawei (IOP Publishing, 2010-02-24) The recursion method of Haydock, Heine and Kelly is a powerful tool for calculating diagonal matrix elements of the resolvent of quantum-mechanical Hamiltonian operators by elegantly expressing them in terms of continued fractions. In this paper we extend the recursion method to off-diagonal matrix elements of general (possibly non-Hermitian) operators and apply it to the simulation of molecular optical absorption and photoemission spectra within time-dependent density-functional and many-body perturbation ...
Constructing sequences with high nonlinear complexity using the Weierstrass semigroup of a pair of distinct points of a Hermitian curve Geil, Olav; Özbudak, Ferruh; Ruano, Diego (Springer Science and Business Media LLC, 2019-06-01) Using the Weierstrass semigroup of a pair of distinct points of a Hermitian curve over a finite field, we construct sequences with improved high nonlinear complexity. In particular we improve the bound obtained in Niederreiter and Xing (IEEE Trans Inf Theory 60(10):6696-6701, 2014, Theorem3) considerably and the bound in Niederreiter and Xing (2014, Theorem4) for some parameters.
New Correlations of m-sequences over the finite field F4 compatible with a new bijection to Z4 Boztas, Serdar; Özbudak, Ferruh; Tekin, Eda (2022-01-01) In this paper we obtain a new method to compute the correlation values of two arbitrary sequences defined by a mapping from F4n to F4. We apply this method to demon-strate that the usual nonbinary maximal length sequences have almost ideal correlation under the canonical complex correlation definition and investigate some decimations giving good cross correlation.
An interactive algorithm for multiobjective ranking for underlying linear and quasiconcave value functions TEZCANER ÖZTÜRK, DİCLEHAN; Köksalan, Mustafa Murat (Wiley, 2019-07-29) We develop interactive algorithms to find a strict total order for a set of discrete alternatives for two different value functions: linear and quasiconcave. The algorithms first construct a preference matrix and then find a strict total order. Based on the ordering, they select a meaningful pair of alternatives to present the decision maker (DM) for comparison. We employ methods to find all implied preferences of the DM, after he or she makes a preference. Considering all the preferences of the DM, the pre...
A new representation for the properties of anisotropic elastic fiber reinforced composite materials Gaith, MS; Akgoz, CY (2005-09-01) A new procedure based on constructing orthonormal tensor basis using the form-invariant expressions which can easily be extended to any tensor of rank n. A new decomposition, which is not in literature, of the stress tensor is presented. An innovational general form and more explicit physical property of the symmetric fourth rank elastic tensors is presented. A new method to measure the stiffness and piezoelectricity in the elastic fiber reinforced composite and piezoelectric ceramics materials using the no...

Citation Formats

H. Ergezer and M. K. Leblebicioğlu, “Refining the progressive multiple sequence alignment score using genetic algorithms,” ARTIFICIAL INTELLIGENCE AND NEURAL NETWORKS, pp. 177–184, 2006, Accessed: 00, 2020. [Online]. Available: https://hdl.handle.net/11511/55007.