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 distance evolution of the best chromosome at each step for - TEST CASE 2.GREEN  =  human-chimpanzee distance, RED  =  human-donkey distance.
© Copyright Policy
Related In: Results  -  Collection


getmorefigures.php?uid=PMC3366991&req=5

pone-0037576-g002: The distance evolution of the best chromosome at each step for - TEST CASE 2.GREEN  =  human-chimpanzee distance, RED  =  human-donkey distance.

Mentions: In the CSSP setting, RD is the only distance that can catch the subtle difference between the human-chimpanzee closest substring and the human-donkey closest substring, even if we use only nucleotides. Hamming and Levenshtein distances are unable to make any difference between the two closest substrings. Figure 2 presents the graphs with the best closest substring candidate according to rank distance, Hamming distance and Levenshtein distance, respectively.


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

Dinu LP, Ionescu R - PLoS ONE (2012)

The distance evolution of the best chromosome at each step for - TEST CASE 2.GREEN  =  human-chimpanzee distance, RED  =  human-donkey distance.
© Copyright Policy
Related In: Results  -  Collection

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

pone-0037576-g002: The distance evolution of the best chromosome at each step for - TEST CASE 2.GREEN  =  human-chimpanzee distance, RED  =  human-donkey distance.
Mentions: In the CSSP setting, RD is the only distance that can catch the subtle difference between the human-chimpanzee closest substring and the human-donkey closest substring, even if we use only nucleotides. Hamming and Levenshtein distances are unable to make any difference between the two closest substrings. Figure 2 presents the graphs with the best closest substring candidate according to rank distance, Hamming distance and Levenshtein distance, respectively.

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