An evolutionary approach to hard test case generation for shortest common superstring problem

Maxim Buzdalov, Fedor Tsarev

Research output: Chapter in Book/Report/Conference proceedingConference Proceeding (Non-Journal item)

1 Citation (Scopus)

Abstract

The shortest common superstring problem has important applications in computational biology (e.g. genome assembly) and data compression. This problem is NP-hard, but several heuristic algorithms proved to be efficient for this problem. For example, for the algorithm known as GREEDY it was shown that, if the optimal superstring has the length of N, it produces an answer with length not exceeding 3.5N. However, in practice, no test cases were found where the length of the answer is greater than or equal to 2N. For hard test case generation for such algorithms the traditional approach assumes creating such tests by hand. In this paper, we propose an evolutionary algorithm based framework for hard test case generation. We examine two approaches: single-objective and multi-objective. We introduce new test case quality measures and show that, according to these measures, automatically generated tests are better than any known ones.

Original languageEnglish
Title of host publicationBRICS-CCI-CBIC '13
Subtitle of host publicationProceedings of the 2013 BRICS Congress on Computational Intelligence and 11th Brazilian Congress on Computational Intelligence
PublisherIEEE Press
Pages81-85
Number of pages5
ISBN (Print)9781479931941
DOIs
Publication statusPublished - 17 Jul 2014
Externally publishedYes
Event1st BRICS Countries Congress on Computational Intelligence, BRICS-CCI 2013 - Recife, Brazil
Duration: 08 Sept 201311 Sept 2013

Publication series

NameProceedings - 1st BRICS Countries Congress on Computational Intelligence, BRICS-CCI 2013

Conference

Conference1st BRICS Countries Congress on Computational Intelligence, BRICS-CCI 2013
Country/TerritoryBrazil
CityRecife
Period08 Sept 201311 Sept 2013

Keywords

  • Evolutionary algorithms
  • Hard test cases
  • Shortest common superstring
  • Test generation

Fingerprint

Dive into the research topics of 'An evolutionary approach to hard test case generation for shortest common superstring problem'. Together they form a unique fingerprint.

Cite this