ACO Implementation for Sequence Alignment with Genetic Algorithms
In this paper, we implement Ant Colony Optimization (ACO) for sequence alignment. ACO is a meta-heuristic recently developed for nearest neighbor approximations in large, NP-hard search spaces. Here we use a genetic algorithm approach to evolve the best parameters for an ACO designed to align two sequences. We then used the best parameters found to interpolate approximate optimal parameters for a given string length within a range. The basis of our comparison is the alignment given by the Needleman-Wunsch algorithm. We found that ACO can indeed be applied to sequence alignment. While it is computationally expensive compared to other equivalent algorithms, it is a promising algorithm that can be readily applied to a variety of other biological problems.
Code (0)
등록된 구현이 없습니다.
Similar Papers 제목 키워드 기반
FPGA Acceleration of Sequence Alignment: A Survey
Genomics is changing our understanding of humans, evolution, diseases, and medicines to name but a few. As sequencing technology is developed collecting DNA sequences takes less time thereby generating more genetic data …
CPUSurveyComputing Phylo-k-mers
Phylogenetically informed k-mers, or phylo-k-mers for short, are k-mers that are predicted to appear within a given genomic region at predefined locations of a fixed phylogeny. Given a reference alignment for this genomi…
Experiments in Linear Template Combination using Genetic Algorithms
Natural Language Generation systems typically have two parts - strategic ('what to say') and tactical ('how to say'). We present our experiments in building an unsupervised corpus-driven template based tactical NLG syste…
SentenceText GenerationSAGA: Synthesis Augmentation with Genetic Algorithms for In-Memory Sequence Optimization
The von-Neumann architecture has a bottleneck which limits the speed at which data can be made available for computation. To combat this problem, novel paradigms for computing are being developed. One such paradigm, know…
Statistically-Consistent k-mer Methods for Phylogenetic Tree Reconstruction
Frequencies of $k$-mers in sequences are sometimes used as a basis for inferring phylogenetic trees without first obtaining a multiple sequence alignment. We show that a standard approach of using the squared-Euclidean d…
Multiple Sequence Alignment