Limits...
An efficient rank based approach for closest string and closest substring.

Dinu LP, Ionescu R - PLoS ONE (2012)

Bottom Line: The two NP-hard problems we are trying to solve are closest string and closest substring.We compare our algorithms with other genetic algorithms that use different distance measures, such as Hamming distance or Levenshtein distance, on real DNA sequences.Our experiments show that the genetic algorithms based on rank distance have the best results.

View Article: PubMed Central - PubMed

Affiliation: Faculty of Mathematics and Computer Science, University of Bucharest, Bucharest, Romania. ldinu@fmi.unibuc.ro

ABSTRACT
This paper aims to present a new genetic approach that uses rank distance for solving two known NP-hard problems, and to compare rank distance with other distance measures for strings. The two NP-hard problems we are trying to solve are closest string and closest substring. For each problem we build a genetic algorithm and we describe the genetic operations involved. Both genetic algorithms use a fitness function based on rank distance. We compare our algorithms with other genetic algorithms that use different distance measures, such as Hamming distance or Levenshtein distance, on real DNA sequences. Our experiments show that the genetic algorithms based on rank distance have the best results.

Show MeSH
The graph of density probability function.
© Copyright Policy
Related In: Results  -  Collection


getmorefigures.php?uid=PMC3366991&req=5

pone-0037576-g006: The graph of density probability function.

Mentions: The graph of this function is represented in Figure 6.


An efficient rank based approach for closest string and closest substring.

Dinu LP, Ionescu R - PLoS ONE (2012)

The graph of density probability function.
© Copyright Policy
Related In: Results  -  Collection

Show All Figures
getmorefigures.php?uid=PMC3366991&req=5

pone-0037576-g006: The graph of density probability function.
Mentions: The graph of this function is represented in Figure 6.

Bottom Line: The two NP-hard problems we are trying to solve are closest string and closest substring.We compare our algorithms with other genetic algorithms that use different distance measures, such as Hamming distance or Levenshtein distance, on real DNA sequences.Our experiments show that the genetic algorithms based on rank distance have the best results.

View Article: PubMed Central - PubMed

Affiliation: Faculty of Mathematics and Computer Science, University of Bucharest, Bucharest, Romania. ldinu@fmi.unibuc.ro

ABSTRACT
This paper aims to present a new genetic approach that uses rank distance for solving two known NP-hard problems, and to compare rank distance with other distance measures for strings. The two NP-hard problems we are trying to solve are closest string and closest substring. For each problem we build a genetic algorithm and we describe the genetic operations involved. Both genetic algorithms use a fitness function based on rank distance. We compare our algorithms with other genetic algorithms that use different distance measures, such as Hamming distance or Levenshtein distance, on real DNA sequences. Our experiments show that the genetic algorithms based on rank distance have the best results.

Show MeSH