Efficient Approaches For DNA Sequences Ordering

The present paper considers an ordering problem inspired from DNA computing, the DNA Sequence Ordering Problem (DNAOP). Since DNAOP is NP-complete, optimal algorithms will prove almost useless in real-world situations. Instead, greedy algorithms turn out to provide efficient alternatives. After a short introduction into the problem field we design two different variants of greedy algorithms. We have tested these variants on diverse datasets and provide the statistical results in graphical form. More precisely, we compare two greedy algorithms (GR and GRM) with three reference algorithms: a random (RAN), an exact (EX) and a lower bound (LB) algorithm. The different behavior of these algorithms is analyzed by experiments. For that purpose test datasets are generated by a random module which allows choosing number (n) and length (k) of DNA-like sequences. The greedy algorithm shows a remarkable efficiency on large datasets.