A memetic algorithm for closest string problem and farthest string problem

Maryam Babaie; Seyed Rasoul Mousavi

doi:10.1109/IRANIANCEE.2010.5507004

A memetic algorithm for closest string problem and farthest string problem

Maryam Babaie, Seyed Rasoul Mousavi

Isfahan University of Technology

Research output: Chapter in Book/Report/Conference proceeding › Conference proceeding › peer-review

7 Citations (Scopus)

Abstract

Sequences consensus problems are especially important in studying molecular evolution, protein structures, and drug target design. In this paper, we work on two of these problems, namely closest string problem and farthest string problem. These problems are NP-hard, and none of exact algorithms already proposed to solve them is in polynomial time. Many non-exact algorithms have been proposed which try to obtain 'good' solutions in acceptable time for these problems. In this paper, a Memetic Algorithm (MA) is proposed for the closest string problem, which outperforms the existing algorithms. We then extend the proposed algorithm to address the farthest string problem.

Original language	English
Title of host publication	Proceedings - 2010 18th Iranian Conference on Electrical Engineering, ICEE 2010
Publisher	IEEE
Pages	570-575
Number of pages	6
ISBN (Print)	9781424467600
DOIs	https://doi.org/10.1109/IRANIANCEE.2010.5507004
Publication status	Published - 8 Jul 2010
Externally published	Yes
Event	2010 18th Iranian Conference on Electrical Engineering, ICEE 2010 - Isfahan, Iran, Islamic Republic of Duration: 11 May 2010 → 13 May 2010

Publication series

Name	Proceedings - 2010 18th Iranian Conference on Electrical Engineering, ICEE 2010

Conference

Conference	2010 18th Iranian Conference on Electrical Engineering, ICEE 2010
Country/Territory	Iran, Islamic Republic of
City	Isfahan
Period	11/05/10 → 13/05/10

Keywords

Bioinformatics
Memetic algorithm
Metaheuristic
String selection problems

ASJC Scopus subject areas

Control and Systems Engineering
Electrical and Electronic Engineering

Access to Document

10.1109/IRANIANCEE.2010.5507004

Cite this

A memetic algorithm for closest string problem and farthest string problem. / Babaie, Maryam; Mousavi, Seyed Rasoul.
Proceedings - 2010 18th Iranian Conference on Electrical Engineering, ICEE 2010. IEEE, 2010. p. 570-575 5507004 (Proceedings - 2010 18th Iranian Conference on Electrical Engineering, ICEE 2010).

Research output: Chapter in Book/Report/Conference proceeding › Conference proceeding › peer-review

Babaie, M & Mousavi, SR 2010, A memetic algorithm for closest string problem and farthest string problem. in Proceedings - 2010 18th Iranian Conference on Electrical Engineering, ICEE 2010., 5507004, Proceedings - 2010 18th Iranian Conference on Electrical Engineering, ICEE 2010, IEEE, pp. 570-575, 2010 18th Iranian Conference on Electrical Engineering, ICEE 2010, Isfahan, Iran, Islamic Republic of, 11/05/10. https://doi.org/10.1109/IRANIANCEE.2010.5507004

@inproceedings{54a8c472c83c45a6a374bb71602f6e61,

title = "A memetic algorithm for closest string problem and farthest string problem",

abstract = "Sequences consensus problems are especially important in studying molecular evolution, protein structures, and drug target design. In this paper, we work on two of these problems, namely closest string problem and farthest string problem. These problems are NP-hard, and none of exact algorithms already proposed to solve them is in polynomial time. Many non-exact algorithms have been proposed which try to obtain 'good' solutions in acceptable time for these problems. In this paper, a Memetic Algorithm (MA) is proposed for the closest string problem, which outperforms the existing algorithms. We then extend the proposed algorithm to address the farthest string problem.",

keywords = "Bioinformatics, Memetic algorithm, Metaheuristic, String selection problems",

author = "Maryam Babaie and Mousavi, {Seyed Rasoul}",

year = "2010",

month = jul,

day = "8",

doi = "10.1109/IRANIANCEE.2010.5507004",

language = "English",

isbn = "9781424467600",

series = "Proceedings - 2010 18th Iranian Conference on Electrical Engineering, ICEE 2010",

publisher = "IEEE",

pages = "570--575",

booktitle = "Proceedings - 2010 18th Iranian Conference on Electrical Engineering, ICEE 2010",

address = "United States",

note = "2010 18th Iranian Conference on Electrical Engineering, ICEE 2010 ; Conference date: 11-05-2010 Through 13-05-2010",

}

TY - GEN

T1 - A memetic algorithm for closest string problem and farthest string problem

AU - Babaie, Maryam

AU - Mousavi, Seyed Rasoul

PY - 2010/7/8

Y1 - 2010/7/8

N2 - Sequences consensus problems are especially important in studying molecular evolution, protein structures, and drug target design. In this paper, we work on two of these problems, namely closest string problem and farthest string problem. These problems are NP-hard, and none of exact algorithms already proposed to solve them is in polynomial time. Many non-exact algorithms have been proposed which try to obtain 'good' solutions in acceptable time for these problems. In this paper, a Memetic Algorithm (MA) is proposed for the closest string problem, which outperforms the existing algorithms. We then extend the proposed algorithm to address the farthest string problem.

AB - Sequences consensus problems are especially important in studying molecular evolution, protein structures, and drug target design. In this paper, we work on two of these problems, namely closest string problem and farthest string problem. These problems are NP-hard, and none of exact algorithms already proposed to solve them is in polynomial time. Many non-exact algorithms have been proposed which try to obtain 'good' solutions in acceptable time for these problems. In this paper, a Memetic Algorithm (MA) is proposed for the closest string problem, which outperforms the existing algorithms. We then extend the proposed algorithm to address the farthest string problem.

KW - Bioinformatics

KW - Memetic algorithm

KW - Metaheuristic

KW - String selection problems

UR - http://www.scopus.com/inward/record.url?scp=77955010862&partnerID=8YFLogxK

U2 - 10.1109/IRANIANCEE.2010.5507004

DO - 10.1109/IRANIANCEE.2010.5507004

M3 - Conference proceeding

AN - SCOPUS:77955010862

SN - 9781424467600

T3 - Proceedings - 2010 18th Iranian Conference on Electrical Engineering, ICEE 2010

SP - 570

EP - 575

BT - Proceedings - 2010 18th Iranian Conference on Electrical Engineering, ICEE 2010

PB - IEEE

T2 - 2010 18th Iranian Conference on Electrical Engineering, ICEE 2010

Y2 - 11 May 2010 through 13 May 2010

ER -

A memetic algorithm for closest string problem and farthest string problem

Abstract

Publication series

Conference

Keywords

ASJC Scopus subject areas

Access to Document

Other files and links

Fingerprint

Cite this