Encoding WordDesign.sm

Name	WordDesign.sm
Class Tree	[Root] Unclassified (114) WordDesignDNA (3)
Submitter	Martin Gebser
Author
Description	CSPLib 033: Word Design for DNA author: Davide Micaletto.
Created	2009-03-30 13:03
Modified	2008-11-29 00:10
Languages	lparse
Language Features
Compatible Instance Classes
Input Predicates
Output Predicates
Encoding Parameter
Standalone	No
Tags
Attributes
Content	%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% % CSPLib 033: Word Design for DNA % SM encoding % author: Davide Micaletto. % % This problem has its roots in Bioinformatics and Coding Theory. % Problem: find as large a set S of strings (words) of length 8 over the alphabet W = { a,c,g,t } % with the following properties: % c1. Each word in S has 4 symbols from { c,g }; % c2. Each pair of distinct words in S differ in at least 4 positions; and % c3. Each pair of words x and y in S (where x and y may be identical) are such that xR and yC % differ in at least 4 positions. Here, ( x1,...,x8 )R = ( x8,...,x1 ) is the reverse of % ( x1,...,x8 ) (P+PR=9) and ( y1,...,y8 )C is the Watson-Crick complement of ( y1,...,y8 ), i.e. % the word where each 1 is replaced by a 2 and vice versa and each 0 is replaced by a 3 and % vice versa (replacement(L1,L2)). % % DATA: % - "letters" represents the set W; % - "max_cardinality" is the problem input and represents the cardinality of S; % - "length" is a constraint representing string length; % - replacement(L1,L2) encodes the replacement function defining the Watson-Crick complement of a string. % % SEARCH SPACE: % - predicate word(N,P,L) means that word N at position P contains the letter L over the alphabet % W = { a,c,g,t }. % - We stored partial information in two predicates, same_letter(N1,N2,P) and same_letter_RC(N1,N2,P) % to model c2 and c3 constraints; % % we modeled this problem as decisional problem increasing the number of words to obtain % optimal solution. %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% #hide. #show word(N,P,L). 1{ word(N,P,L): letters(L) }1:- words(N), positions(P). 4{ word(N,P,L): letters(L): positions(P): or(eq(L,c),eq(L,g)) }4:- words(N) . %%% c1 same_letter(N1,N2,P) :- word(N1,P,L), word(N2,P,L), positions(P), letters(L), words(N1;N2), neq(N1,N2). :- 5{ same_letter(N1,N2,P): positions(P) }, words(N1;N2), neq(N1,N2). %%% c2 same_letter_RC(N1,N2,P) :- word(N1,9-P,L), word(N2,P,L1), replacement(L,L1), positions(P), letters(L;L1), words(N1;N2). :- 5{ same_letter_RC(N1,N2,P) : positions(P)}, words(N1;N2). %%% c3

Actions

Navigation

Encoding WordDesign.sm