- Experimentation with the directed graph CSP formulation described by Meneses et al. [17] to improve their IP formulation as an alternative CSP model for closest strings
- Investigating other NP-hard string sequence problems such as closest substring, farthest string and n-mismatch - an obvious candidate is consensus string, which differs from closest string only in that the objective is to minimise the sum of the distances, rather than minimise the maximum individual distance
- Search for more complicated metrics than Hamming distance that better capture the concepts of difference and similarity for nucleotide sequences - recent results involving Markov models [24] suggest that judicious choice of metric has profound implications for both the theory and practice of identifying self-similarity amongst sequences.

## 4.2 Acknowledgments

The authors would like to acknowledge the critical discussions had with Prof. Ian Gent and Dr. Ian Miguel, and with various attendees at the International Society for Computational Biology's Latin America meeting held in Montevideo, Uruguay in March 2010. Tom Kelsey is supported by UK Engineering and Physical Sciences Research Council (EPSRC) grants EP/CS23229/1 and EP/H004092/1. Lars Kotthoff is supported by a Scottish Informatics and Computer Science Alliance (SICSA) studentship. The funders had no role in study design, data collection and analysis, decision to publish, or preparation of the manuscript.

## References

[1] Christian Bessiere and Romuald Debruyne. Theoretical analysis of singleton arc consistency and its extensions. *Artif. Intell.*, 172(1):29–41, 2008.

[2] F. Chin and H. C. Leung. DNA motif representation with nucleotide dependency. *IEEE/ACM transactions* on computational biology and bioinformatics / IEEE, ACM, 5(1):110–119, 2008.

[3] Zeev Collin, Rina Dechter, and Shmuel Katz. On the feasibility of distributed constraint satisfaction. In IJCAI'91: Proceedings of the 12th international joint conference on Artificial intelligence, pages 318–324.

Morgan Kaufmann Publishers Inc., 1991.

[4] Andreas Distler, Chris Jefferson, Tom Kelsey, and Lars Kotthoff. The semigroups of order ten. In preparation, 2010.

[5] Andreas Distler and Tom Kelsey. The monoids of orders eight, nine & ten. *Ann. Math. Artif. Intell.*, 56(1):3–
21, 2009.

[6] Eran Eden, Doron Lipson, Sivan Yogev, and Zohar Yakhini. Discovering motifs in ranked lists of DNA
sequences. *PLoS Comput Biol*, 3(3):e39+, March 2007.

[7] O. Etzioni, T. Ishida, and N. Jennings, editors. *Distributed constraint satisfaction: foundations of cooperation* in multi-agent systems. Springer-Verlag, London, UK, 2001.

[8] Ester Falconer, Elizabeth A. Chavez, Alexander Henderson, Steven S. Poon, Steven McKinney, Lindsay Brown, David G. Huntsman, and Peter M. Lansdorp. Identification of sister chromatids by DNA template strand sequences. *Nature*, 463(7277):93–97, January 2010.

[9] Moti Frances and Ami Litman. On covering problems of codes. *Theory Comput. Syst.*, 30(2):113–119, 1997.

[10] Ian P. Gent, Christopher Jefferson, and Ian Miguel. Minion: A fast scalable constraint solver. In Gerhard Brewka, Silvia Coradeschi, Anna Perini, and Paolo Traverso, editors, *ECAI*, volume 141 of Frontiers in Artificial Intelligence and Applications, pages 98–102. IOS Press, 2006.

[11] Jens Gramm, Rolf Niedermeier, and Peter Rossmanith. Exact solutions for closest string and related problems. In *ISAAC '01: Proceedings of the 12th International Symposium on Algorithms and Computation*,
pages 441–453, Berlin, Heidelberg, 2001. Springer-Verlag.