/ Code author: Dennis Shasha, 2002 / We infer circuits as follows: / Take the Exper relationship / There is also a list of values of the independent / attributes that represents the base values. / We compare every other configuration with that one. / If the difference is significant, we look at the direction / and print out the differences in the values for that attribute list. / TIME TESTING / \l time / SET STUFF /finds intersection of two lists / fastest of all intersect: {[x;y] x,: () y,: () if[(#x) < (#y) i: x ?/: y j: & i < #x :x[?i[j]] ] i: y ?/: x j: & i < #y :y[?i[j]] } /finds intersection of two lists / fastest of all hasintersect: {[x;y] x,: () y,: () i: x ?/: y : (&/i) < #x } / x is a proper subset of y propersubset:{[x;y] x,: () y,: () if[~ (#x) < (#y); :0] / must be smaller :(#x) = (#intersect[x;y]) } subset:{[x;y] (#x) = (#intersect[x;y])} subset:{[x;y] j: y ?/: x / if any js are as big as #y, then there is a member of x not in y :0 = |/ j = #y } / proportion of x that y covers approxsubset:{[x;y] j: y ?/: x / any equal to #y are in x but not in y :(# & j < (#y)) % (#x) } / finds indexes in x and y that intersect / If x and y are both sets, then the results will be of the same length / fastest of all intersectindexes: {[x;y] i: x ?/: y / where each y hits j: & i < #x / those ys that hit :(i[j];j) } /finds indexes in x that intersect with y intersectleftindexes: {[x;y] i: x ?/: y / where each y hits j: & i < #x / those ys that hit :i[j] } / finds indexes in x that intersect with y / even if x is a multiset intersectleftindexes_multi: {[x;y] k: y ?/: x : & k < #y } /finds intersection of two lists / and returns index pairs of matches. Assumes no duplicates / in either list intersectbothindexes: {[x;y] x,: () y,: () i: x ?/: y pairs: (i ,' (!#y)) k: & pairs[;0] < #x :pairs[k] } / this is a set intersection so we remove duplicates multiintersect:{[lists] size: #lists if[0 = #lists; :()] / if[2 > size; :lists] if[2 > size; :*lists] first: lists[0],() jj: first ?/: (,/ ?:' lists[1+ !(size-1)]) / find indexes in first x: @[(1+#first) # 0; jj; + ; 1] x: (-1) _ x / delete missing entry kk: & x = size - 1 :first[kk] } / this is a set intersection so we remove duplicates / just like multiintersect except that the maxdist allows / a result if it is present in (#lists) - maxdist / of the input lists threshintersect:{[lists; maxdist] size: #lists if[2 > size; :lists] / first: lists[0],() / no good because might be empty first: (?,/lists) ,() / union / jj: first ?/: (,/ ?:' lists[1+ !(size-1)]) / find indexes in first jj: first ?/: (,/ ?:' lists) / find indexes in first x: @[(1+#first) # 0; jj; + ; 1] x: (-1) _ x / delete missing entry / kk: & x > size - (2 + maxdist) kk: & x > size - (1 + maxdist) :first[kk] } / A faster difference differ:{[x;y] x,: () y,: () i: y ?/: x j: & i = #y :?x[j] } / Count the difference differcount:{[x;y] i: y ?/: x :# & i = #y } / END OF SET STUFF / READ IN / a list is numeric if each member is either empty, a period / or a digit isnumeric:{[list] s: ,/list nums: "1234567890" x: nums ?/: s y: (#nums) > |/x / if greater then everything in s met its match if[1 = y; :2] / 2 means integer nums: "1234567890." x: nums ?/: s :(#nums) > |/x / if greater then everything in s met its match / 1 means float and 0 means not a number } / parses a field based on vertical bars getfields:{[line] i: line = "|" j1: &i j2: &~i line @:j2 size: #j1 :(0,(j1 - !size)) _ line } / get rid of blanks at either end of the string delendblanks:{[string] if[0 = #string; :""] if[string ~ ,"" ; :""] i: & ~ string = " " if[(#string) = (#i); :string] if[0 = (#i); :""] string: (- ((#string) - (1 + *|i))) _ string :(*i) _ string } / Handles one line of input at a time according to table schema above. / A little more space efficient than the previous version. processline:{[line] emptyorblank:{[line] (0 = #delendblanks[line])} emptyflag: emptyorblank[line] if[~emptyflag justempty:: 0 if[line[0] = "#" newline: delendblanks'getfields[1 _ line] if[(1 < #newline) globaltable:: *newline alltables,: ` $ globaltable globalatt:: 1 _ newline globalvals:: () / initialize ] / newline ] / table declaration if[~ line[0] = "#" newline: delendblanks'getfields[line] if[(1 < #newline) | (0 < #newline[0]) globalvals,: ,newline ] ] / end of test on data line ] / end of test on line is non-empty if[emptyflag & (0 = justempty) justempty:: 1 / if[ ((#globalatt) > 1) | (~ (#globalatt) = (^globalvals)[0]) / globalvals:: + globalvals / take transpose / ] if[~ (#globalatt) = (#globalvals[0]); !-1] numericflag:() hh: 0 while[hh < #globalatt numericflag,: isnumeric[globalvals[;hh]] hh+: 1 ] inindex:: 0 while[inindex < #globalatt / table.att[2] :: ` $ vals[3] string1: globaltable, (".") string1,: globalatt[inindex] teststring: ("0 = #"), string1 / For big sizes, uncomment following two statements / User will get an error message, but it will work. / x: @[.: ; teststring; :] / currentlyempty: *x / error means empty / For big sizes, comment following currentlyempty: 1 / if empty, then assign, else append string2: :[currentlyempty; (":: "); (",: ")] string3: :[0 = numericflag[inindex] "` $ " :[1 = numericflag[inindex]; "0.0 $ "; "0 $ "]] string3,: "globalvals[;inindex]" . string1, string2, string3 if[1 = numericflag[inindex] globalindexes:: & 0N = . string1 string3: string1, ("[globalindexes] :: `") . string3 ] inindex+: 1 ] ] } inputfromfile:{[filename] a: 0: filename globalvals:: () oldglobalvals:: () / should not be necessary justempty:: 1 / as if we've just seen an empty line. should process table a,: ,,"" processline'a makeintlist:{[line] (. $line), ()} tree.childrenid:: makeintlist'tree.childrenid } / DUMP TABLE dumptable / formstring takes a list and makes a string formstring:{[list] list,: () : (-1) _ ,/ ($list) ,\: (" ") } formstringvertbar:{[list] list,: () : (-1) _ ,/ ($list) ,\: ("|") } formstringcomma:{[list] list,: () : (-1) _ ,/ ($list) ,\: (",") } / Output a table (a variable) to a text file outfile (string) / e.g. output[`guide; guide; "foobar"] dumptable:{[tablename; table; outfile] out: ,("# "), ($tablename), ("|"), formstringvertbar[!table] first: *!table numofelements: . ("#"), ($tablename), ("."), ($first) i: 0 while[i < numofelements list: table[;i] x: formstring'list out,: , (-1) _ ,/x ,\: ("|") i+: 1 ] outfile 0: out } dumptablecsv:{[tablename; table; outfile] out: , formstringcomma[!table] first: *!table numofelements: . ("#"), ($tablename), ("."), ($first) i: 0 while[i < numofelements list: table[;i] x: formstring'list out,: , (-1) _ ,/x ,\: (",") i+: 1 ] outfile 0: out } / APPLICATION SPECIFIC / given the outvalues of good rows, try to find / pairs of attribute-values that together give synergistic effects / For this we have to find three good rows, / one has attribute-values X, the other Y, and the other a combination / of the two. The idea is that the third should combine the virtues / of the other two. / outvals has the output values of the good ones whereas values / are for all experiments. findsynergies:{[good; outvals; values; attlist] a: avg[outvals] if[a < 1 outvals: 1 % outvals / invert it ] s: std[outvals] ii: & outvals > a + s reallygood: good[ii] justgood: good _di ii if[0 = #reallygood; :()] contextvals: values[reallygood] number: #:' ?:' + contextvals mm: & 1 = number values: values[;mm] attlist: attlist[mm] disjunctlist: () size: 1 while[size < 3 / as of now just go up to that size - 1 pair: createcircuit[size; reallygood; justgood; values; attlist] new: pair[0] zz: 0 / squeeze out new combinations that are supersets of old ones while[zz < #disjunctlist hh: & subset[disjunctlist[zz]]'new new: new _di hh zz+: 1 ] disjunctlist,: new good: differ[good; pair[1]] / eliminate some good indexes size+: 1 ] :disjunctlist } formcircuit:{[good; bad; values; attlist] disjunctlist: () size: 1 while[size < 3 / as of now just go up to that size - 1 pair: createcircuit[size; good; bad; values; attlist] disjunctlist,: pair[0] good: differ[good; pair[1]] / eliminate some good indexes size+: 1 ] :disjunctlist } / given indexes of good experiments (with desired result, e.g. repressive) / and bad ones and given the values of the context (with attribute names), / try to form a hypothesis. / An amplifier X has the property that X alone does not cause induction / Y causes induction by itself but X and Y cause strong induction. / In that case, X is an amplifier for Y. / If X and Y each cause induction but X and Y together cause more, / then they are synergistic. createcircuit:{[size; good; bad; values; attlist] if[0 = #good; :(();())] combos: cartesian[size; !#attlist] / cartesian product of attribute names / up to size size, e.g. Illumination, Starvation, NH3 / These would be possible distinguishing attributes. outattval: () outused: () goodvalues: values[good] / values of the contextual attributes / when output is good badvalues: values[bad] i: 0 while[i < #combos mygoodvals: goodvalues[;combos[i]] / project onto candidate combo mybadvals: () / may be none if[0 < #badvalues mybadvals: badvalues[;combos[i]] ] diff: differ[(?mygoodvals); (?mybadvals)] / good and bad differ there / on those attributes in the combo if[0 < #diff / have found something j: 0 while[j < #diff jj: & mygoodvals ~\: diff[j] outused,: good[jj] / indexes of experiments / that have these values outattval,: ,attlist[combos[i]] ,' diff[j] / these attributes with these values / differentiate the good from the bad. j+: 1 ] ] i+: 1 ] outattval: sort'outattval :(?outattval; ?outused) } sort:{[list] list @ < list} spit:{[pair] ` $ ($pair[0]), ("_"), ($pair[1])} spitcomma:{[inds] (-1) _ ,/ ($inds) ,\: (",")} / take the cartesian product of a set size times cartesian:{[size; set] out: ,:' set i: 1 while[i < size out: ,/ out ,/:\: set i+: 1 ] :out } spitcircuit:{[list] out: () i: 0 while[i < #list if[1 = #list[i] out,: ,* ($spit'[list[i]]) ] if[1 < #list[i] x: (-5) _ ,/ ($spit'list[i]) ,\: (" and ") out,: ,x ] i+: 1 ] :out } / generate experiments given good and bad experimenal conditions generateexperiment:{[good; bad; values; attlist] goodvalues: values[good] goodindexes: !#goodvalues badvalues: values[bad] badindexes: !#badvalues combos: ,/goodindexes ,/:\: badindexes i: 0 mindiff: #attlist / number of attributes bestcomboindex: ,0 / best combo while[i < #combos mygood: goodvalues[combos[i;0]] mybad: badvalues[combos[i;1]] countdiff: #& ~ mygood = mybad if[countdiff = mindiff bestcomboindex,: i ] if[countdiff < mindiff bestcomboindex: ,i mindiff: countdiff ] i+: 1 ] outexper: () i: 0 while[i < #bestcomboindex myindex: bestcomboindex[i] mygood: goodvalues[combos[myindex][0]] mybad: badvalues[combos[myindex][1]] outexper,: genexper[mygood; mybad; attlist] i+: 1 ] :outexper } / given two close contexts, generate experiments genexper:{[gvals; bvals; attlist] origexper: gvals outexper: () jj: & ~ gvals = bvals i: 0 while[i < #jj x: origexper myindex: jj[i] x[myindex]: bvals[myindex] outexper,: ,spit'attlist,'x i+: 1 ] :outexper } / find out minimum distance of a member of conds to leftcond findmindist:{[conds;leftcond] if[0= #conds; :0] :&/ (#leftcond) - (+/'conds =\: leftcond) } / find the cross product of a bunch of lists and return them to / strings crossprod:{[lists] if[0 = #lists; :()] out: lists[0] i: 1 while[i < #lists out: ,/ out ,/:\: (lists[i],()) i+: 1 ] :,/' $out } / if already numbers or a string, send back / if symbols, then convert to numbers letconvert:{[list] if[(4: list) _in -3 -1; :list] ii: &list _in\: `N `D jj: &list _in\: `Y `L list[ii]: 0 list[jj]: 1 :list } / New strategy for generating experiments. / indconds -- inductive conditions / repconds -- repressive conditions / allindvals -- all conditions of all attributes / Generate all possible experiments as cross product of allindvals. / Then look for those that are not already represented in indconds or / repconds and / then find those that are close both to one class and to the other. / Generating all experiments may become expensive, so do only on request. findcands:{[indconds; repconds; attvallist] allindvals: letconvert'attvallist allconds: crossprod[allindvals] leftconds: differ[allconds; indconds,repconds] if[0 = #leftconds; :()] / nothing to do toind: findmindist[indconds]'leftconds torep: findmindist[repconds]'leftconds if[0 < (#indconds) & (#repconds) / then look for minimum border cases tots: toind+torep mintot: &/tots ii: & tots = mintot :leftconds[ii] ] / look for maximum difference from what you have done / to see if you can find anything tots: torep maxtot: |/tots ii: & tots = maxtot :leftconds[ii] } / APPLICATION SPECIFIC PART OF BOOLEAN (OR EXTENDED BOOLEAN) OPTIMIZATION / Reduces a list of extended boolean conditions in / disjunctive normal form (disjunction of conjuncts) to a smaller / set with don't cares. / attvallist is a list of lists. / Each list has the possible values of the attributes / e.g. if binary 0 and 1 / Goodvals is a list of good boolean (or multivalued) combinations in the order / of the attributes of the attvallist. / Algorithm: / The condition for reducing a set of combinations to / a single one with a don't care is the following: / Consider attribute A. Suppose that there is a set of combinations / that are identical on all attributes other than A and that include / every possible A value. Then reduce that entire set to one in which / the A value is just a dash "-". / We can create don't cares in any order though we may want to / use the don't care guys in some way, e.g. / 000 / 001 / 010 / 011 / If all three attributes are boolean then we will get / 00- / 01- / Then we will know that we have 0--, so we can treat / dashes like anything else. / get the partitions based on all attributes except / attribute i. getpart:{[i; combinations] out: (#combinations) # ,() j: 0 while[j < #combinations[0] if[~ j = i out: out ,' combinations[;j] ] j+: 1 ] part: = out :part } / find reduction even if not boolean / goodvals are those combinations that give the desired output / e.g. / 0111 / 0101 / 0100 / 0001 / 0000 / 0201 / 0200 / attvallist are the possible values for each attribute value / e.g. attvallist / 012 / 012 / 01 / 01 / Result is: / 01-1 / 0-0- reduce:{[goodvals; attvallist] newgoodvals: ? goodvals flag: 1 / Try to get a - as much as possible while[flag flag: 0 / only turn to 1 if you change something i: 0 while[i < #attvallist part: getpart[i; newgoodvals] counts: #:' part / kk: & counts = #attvallist[i] kk: & (counts = #attvallist[i]) & (counts > 1) part@: kk / these are the ones that we are going to reduce / newout: newgoodvals[differ[!#newgoodvals; ,/part]] newout: newgoodvals / keep all of them / we want all of these. The others will be reduced if[0 < #kk firsts: newgoodvals[*:' part] firsts[;i]: `"-" firsts: differ[firsts; newgoodvals] if[0 < #firsts newout,: firsts flag: 1 ] ] newgoodvals: newout i+: 1 ] ] x: elimredun[newgoodvals] / get rid of those constant ones / determined by others / Now for each one left, see if it is covered by others x: elimcovered[goodvals; x] :,/'$x } / see whether valvec2 is a specialization of valvec1 rightredundant:{[valvec1; valvec2] i: 0 while[i < #valvec1 if[(~ valvec1[i] ~ `"-") & (~valvec1[i] ~ valvec2[i]) :0 ] i+: 1 ] :1 } convertquest:{[pat] newpat: ,/$pat ii: &newpat = "-" newpat[ii]: "?" :newpat } / get rid of patterns that are covered by others elimcovered:{[goodvals; pats] newpats: convertquest'pats match: () i: 0 while[i < #newpats match,: ,& goodvals _sm\: newpats[i] i+: 1 ] stillin: !#match i: 0 while[i < #match if[subset[match[i]; ,/match[stillin _dv i]] stillin: stillin _dv i ] i+: 1 ] :pats[stillin] } / eliminate any row that is the same as another row except it has / don't cares elimredun:{[goodvals] badind: () ind: !#goodvals i: 0 while[i < #goodvals j: 0 while[j < #goodvals if[~ i = j if[rightredundant[goodvals[i]; goodvals[j]] badind,: j ] ] j+: 1 ] i+: 1 ] :goodvals[differ[(!#goodvals); ?badind]] } / END APPLICATION SPECIFIC FOR BOOLEAN REDUCTION / APPLICATION SPECIFIC / given two sets of values where D means 0 and L means 1 and / N means 0 and Y means 1, find what makes newguy different from baseguy / UNUSED finddifferold:{[newguy; baseguy] out: () i: 0 while[i < #newguy if[newguy[i] = baseguy[i]; out,: "-"] if[~ newguy[i] = baseguy[i] if[newguy[i] _in `Y `L; out,: "1"] if[newguy[i] _in `N `D; out,: "0"] ] i+: 1 ] :out } / Now we think that we need the ones that are the same and different finddiffer:{[newguy; baseguy] out: () i: 0 while[i < #newguy if[newguy[i] _in `Y `L; out,: "1"] if[newguy[i] _in `N `D; out,: "0"] i+: 1 ] :out } / return indexes of input that are non-redundant / UNUSED simplify:{[vals] if[0 = #vals; :()] i: 0 while[i < #vals vals[i]: (vals[i])[!(vals[i] ? " ")] i+: 1 ] outind: () i: 0 while[i < #vals j: 0 while[j < #vals if[~ i = j kk: & ~ vals[i] = "-" kk2: & ~ vals[j] = "-" if[(subset[kk2; kk]) / then i may unnecessarily / specify more values than it needs if[((vals[i])[kk2]) ~ ((vals[j])[kk2]) / it does outind,: i ] ] ] j+: 1 ] i+: 1 ] :differ[!#vals; ?outind] } / uses Exper already corrected / (targetname is dependent attribute (e.g. ASN1) and targetval is the value) / independentatts has the names of the independent attributes of interest / targetatt is the dependent attribute / indbasevals are the values of the independent attributes / in order that constitute the base case. / For example, the indbasevals may be no carbon, no light, no starvation ... / Algorithm: Project Exper on the independentatts in the order they are given / This gives a projection of Exper on those attributes. / This gives a matrix. Then find those that have indbasevals. / Then compare the target values for the base case / against the target values for each other possible combination / of independent value. / If a combination has a significant difference, then indicate / that difference and print it out along with the differences / in the new one that cause the difference in output. / At the very end, perform a reduction of the output according to a / boolean reduction. findcircuits:{[independentatts; indbasevals] findcandidatesflag: 1 / do this if you want candidates string: () attvallist: () / all values of an independent attribute i: 0 while[i < #independentatts string,: ("Exper."),($independentatts[i]),(" ,' ") mystring: ("Exper."),($independentatts[i]) attvallist,: ,? . mystring / get the possible values for that attribute i+: 1 ] string: (-4) _ string allindvals: . string part: = allindvals uniqs: ?allindvals baseindex: uniqs ? indbasevals if[baseindex = #uniqs / !-1 / most probably indbasevals is nowhere present in the data ` 0: ,"indbasevals is nowhere present in the data" . "\\\\" ] targname: Exper.targetname[0] / they had better all be the same alltargvals: Exper.targetval[part] / We now have the matrix and the values. / Now we compare all to the base. out: ,($targname) out,: ,spitcomma[independentatts] out,: ,"L,S,C,N,E,Q" out,: ,"1,2,3,4,4,4" out,: , ("base values are: "), spitcomma[indbasevals], ("(D=0;N=0)") outreadable: out outind: ,"inductive" outrep: ,"repressive" outsupind: ,"superinductive" outsuprep: ,"superrepressive" indflag: 0 indsupflag: 0 repflag: 0 repsupflag: 0 i: 0 while[i < #uniqs if[~ i = baseindex q: tnopairevaluate[alltargvals[i];alltargvals[baseindex]] adiff: (avg[alltargvals[i]]) % (avg[alltargvals[baseindex]]) d: finddiffer[uniqs[i]; uniqs[baseindex]] if[(q[1] = 1) & (q[3] = `inductive) if[~ adiff > 10 outind,: ,d indflag: 1 ] if[adiff > 10 outsupind,: ,d indsupflag: 1 ] ] if[(q[1] = 1) & (q[3] = `repressive) if[~ adiff < 0.1 outrep,: ,d repflag: 1 ] if[adiff < 0.1 outsuprep,: ,d repsupflag: 1 ] ] ] i+: 1 ] indconds: () repconds:() / ??? Save all the outind, outsupind etc. / and then we can intersect / them later. These have no dontcares / Our idea is simple: take the intersection and then / later perform this same analysis. / That is, do the reduce etc. "outind" 0: outind "outsupind" 0: outsupind "outrep" 0: outrep "outsuprep" 0: outsuprep "attvallist" 1: attvallist if[indflag indconds,: 1 _ outind x: reduce[1 _ outind; attvallist] out,: (,*outind), x outreadable,: (,*outind), spitcomma'x / out,: (,*outind), reduce[(1 _ outind),(1 _ outsupind); attvallist] ] if[indsupflag indconds,: 1 _ outsupind x: reduce[1 _ outsupind; attvallist] out,: (,*outsupind), x outreadable,: (,*outsupind), spitcomma'x ] if[repflag repconds,: 1 _ outrep x: reduce[1 _ outrep; attvallist] out,: (,*outrep), x outreadable,: (,*outrep), spitcomma'x / out,: (,*outrep), reduce[(1 _ outrep),(1 _ outsuprep); attvallist] ] if[repsupflag repconds,: 1 _ outsuprep x: reduce[1 _ outsuprep; attvallist] out,: (,*outsuprep), x outreadable,: (,*outsuprep), spitcomma'x ] candtests: () if[findcandidatesflag candtests: ,($targname) candtests,: ,spitcomma[independentatts] candtests,: ,("base values are: "),spitcomma[indbasevals], ("(D=0;N=0)") candtests,: spitcomma'findcands[indconds; repconds; attvallist] / find candidate tests that distinguish inductive from / repressive cases and are close to both. ] :(out; outreadable; candtests) } / END OF SKELETON goodvals: ("110101" "011010" "001111" "001100" "001101" "100101" "010011" "100111" "000111" "000001" "000010" "000100" "000110" "001001" "001010" "001011" "010000" "010001" "010111") attvallist: (`D `L `N `Y `N `Y `N `Y `N `Y `N `Y) reduce[goodvals; attvallist]