“School of Biological Sciences”
Back to Papers HomeBack to Papers of School of Biological Sciences
| Paper IPM / Biological Sciences / 13237 |
|
||||||||||||
| Abstract: | |||||||||||||
|
Construction of two haplotypes from a set of Single Nucleotide Polymorphism (SNP) fragments is
referred to as haplotype reconstruction problem. One of the most important computational models for
this problem is Minimum Error Correction (MEC). Since MEC is an NP-hard problem, here we
propose a heuristic algorithm for haplotype reconstruction problem. The algorithm is Particle Swarm
Optimization (PSO) which is an evolutionary algorithm (EA). Evolutionary algorithms are stochastic
search algorithms that imitate the natural biological evolution or the social behavior of species. In
contrast to MEC model, our algorithm produces results in feasible time and it could be applied to large
datasets. Our results suggest that the algorithm has less reconstruction error rate compared to other
algorithms. This error is also very close to zero when the algorithm is applied to actual biological data.
A comprehensive comparison between PSO and four famous algorithms in the literature is presented.
A discussion on input parameters influencing reconstruction error rate is also presented.
More info: http://match.pmf.kg.ac.rs/electronic_versions/Match62/n2/match62n2_261-274.pdf
Download TeX format |
|||||||||||||
| back to top | |||||||||||||
