Solving the Minimum Common String Partition Problem with the Help of Ants

2014/01/18 by S. M. Ferdous, Ferdous, S. M., M. Sohel Rahman +1
Biochemistry, Genetics and Molecular Biology · Computer Science · #Algorithms and Data Compression #Artificial Intelligence (cs.AI) #DNA and Biological Computing #FOS: Computer and information sciences #Genome Rearrangement Algorithms

paper · pdf · doi:10.48550/arxiv.1401.4539

openalex publication_date 2014/01/18 · openalex created_date 2022/11/30 · openalex updated_date 2026/07/28

Abstract

In this paper, we consider the problem of finding a minimum common partition of two strings. The problem has its application in genome comparison. As it is an NP-hard, discrete combinatorial optimization problem, we employ a metaheuristic technique, namely, MAX-MIN ant system to solve this problem. To achieve better efficiency we first map the problem instance into a special kind of graph. Subsequently, we employ a MAX-MIN ant system to achieve high quality solutions for the problem. Experimental results show the superiority of our algorithm in comparison with the state of art algorithm in the literature. The improvement achieved is also justified by standard statistical test.

Related

• On Solving the Minimum Common String Partition Problem by Decision Diagrams
• Mathematical Programming Strategies for Solving the Minimum Common String Partition Problem
• A Fixed-Parameter Algorithm for Minimum Common String Partition with Few Duplications
• Minimum Common String Partition Parameterized by Partition Size is Fixed-Parameter Tractable
• A Dynamic Algorithm for the Longest Common Subsequence Problem using Ant Colony Optimization Technique