Debian Codegraph @

metastudentPkg/lib/groupB/pp2/prediction/knn/PredictionTarget.java

raw
1 package pp2.prediction.knn;
2
3 import java.io.BufferedWriter;
4 import java.io.IOException;
5 import java.util.Collections;
6 import java.util.HashSet;
7 import java.util.Vector;
8
9 import pp2.go.DAG;
10 import pp2.go.Relations;
11 import pp2.tools.Tools;
12
13 /**
14 * represents one function prediction target which is given in the BLAST results file
15 * @author Thomas Hopf
16 *
17 */
18 public class PredictionTarget {
19
20 public static final int NUM_ONTOLOGIES = 3;
21 public static final int BIOLOGICAL_PROCESS = 0;
22 public static final int MOLECULAR_FUNCTION = 1;
23 public static final int CELLULAR_COMPONENT = 2;
24
25 public static final double MAX_EVALUE = 1000;
26
27 private static String newline = System.getProperty("line.separator");
28 private static String tab = "\t";
29
30 private String targetID;
31 private Vector<BlastHit> blastHits = new Vector<BlastHit>();
32
33 /*
34 * getters and setters
35 */
36 public void setTargetID(String targetID) {
37 this.targetID = targetID;
38 }
39
40 public String getTargetID()
41 {
42 return targetID;
43 }
44
45 public void addBlastHit(String hitLine, boolean deleteDuplicates)
46 {
47 if(deleteDuplicates)
48 {
49 String newID = hitLine.split("\t")[0];
50 for(int i=0; i<blastHits.size(); i++)
51 {
52 if(blastHits.get(i).getHitID().equals(newID))
53 blastHits.remove(i);
54 }
55 }
56
57 blastHits.add(new BlastHit(hitLine));
58 }
59
60 public Vector<BlastHit> getBlastHits()
61 {
62 return blastHits;
63 }
64
65 /*
66 * methods
67 */
68
69 private int ontologyToIndex(String ontology)
70 {
71 if(ontology.equals("molecular_function"))
72 return MOLECULAR_FUNCTION;
73 else {
74 if(ontology.equals("biological_process"))
75 return PredictionTarget.BIOLOGICAL_PROCESS;
76 else
77 return PredictionTarget.CELLULAR_COMPONENT;
78 }
79 }
80
81 // private double limitRange(double value)
82 // {
83 // return Math.max(1E-308, Math.min(value, 1));
84 // }
85
86 private double getExponent(double eValue)
87 {
88 if(eValue <= 0)
89 return MAX_EVALUE;
90 else
91 return -Math.log(eValue);
92 }
93
94 private String indexToOntology(int index)
95 {
96 switch(index)
97 {
98 case BIOLOGICAL_PROCESS: return "B";
99 case MOLECULAR_FUNCTION: return "M";
100 case CELLULAR_COMPONENT: return "C";
101 default: return "-";
102 }
103 }
104
105 public void predict(Relations relations, boolean useEValueThreshold, double eValueTreshold, int k, BufferedWriter naiveWriter, BufferedWriter leafWriter, double[] distribution) throws Exception
106 {
107 // System.out.println("predicting " + targetID);
108
109 // System.out.print(".");
110 // if we don't have any BLAST hits for the current target, predicting anything is pointless...
111 if(blastHits.size() == 0)
112 return;
113
114 // sort result list in ascending order by e-Value
115 Collections.sort(blastHits);
116
117 // create a vector containing only the relevant Blast hits, i.e. those with an e-Value
118 // below the threshold or the first k nearest neighbors
119 Vector<BlastHit> blastHitsTmp = new Vector<BlastHit>(blastHits.size());
120
121 int j=0;
122
123 while(j < blastHits.size() && blastHits.get(j).getEValue() <= eValueTreshold && j < k)
124 {
125 blastHitsTmp.add(blastHits.get(j));
126 j++;
127 }
128
129
130 // calculate the global quality score of this hit (i.e. the quantile of mean(E-Values) + 2*stddev(E-values)
131 double quantile = 1;
132
133 if(distribution != null)
134 {
135 // first, calculate mean
136 double mean = 0;
137
138 for(BlastHit b: blastHitsTmp)
139 mean += getExponent(b.getEValue());
140
141 mean /= blastHitsTmp.size();
142 //System.out.println("mean " + mean);
143
144 // second, calculate standard deviation
145 double stdDev = 0;
146
147 for(BlastHit b: blastHitsTmp)
148 stdDev += (getExponent(b.getEValue()) - mean) * (getExponent(b.getEValue()) - mean);
149
150 // unbiased estimator: normalize by N-1
151 stdDev = Math.sqrt(stdDev / (blastHitsTmp.size() - 1));
152 //System.out.println("sd " + stdDev);
153
154 // calculate quality score as mean+2*stddev
155 double qualityScore = mean + 2*stdDev;
156 //System.out.println("score " + qualityScore);
157
158 // find which quantile the quality score corresponds to. This is the global quality score of the target
159 int i = 0;
160 while(i<100 && qualityScore >= distribution[i])
161 i++;
162
163 quantile = (i + 1)/(double)100;
164 //System.out.println("quantile :" + quantile);
165 }
166
167
168 // System.out.println("before: " + blastHits.size() + " => after: " + blastHitsTmp.size());
169
170 // for(BlastHit b: blastHits)
171 // {
172 // System.out.println(b.getHitID() + ": " + b.getEValue());
173 // }
174
175 /*
176 * step 1: get a list of all unique GO terms of hits for this prediction and construct the DAG
177 *
178 * TODO: this is a bit redundant since DAG.java also converts the String[] parameter to a HashSet
179 */
180 HashSet<String> allGoTerms = new HashSet<String>();
181 int totalNumGoTerms = 0;
182
183 for(BlastHit b : blastHitsTmp)
184 for(String s : b.getGoTerms())
185 {
186 allGoTerms.add("GO:" + s);
187 totalNumGoTerms++;
188 }
189
190 DAG dag = new DAG(relations, (String [])allGoTerms.toArray(new String[0]));
191 HashSet<BlastHit> normalizationHits = new HashSet<BlastHit>();
192
193 // check whether there are any valid nodes or if we lost everything due to filtering cellular component annotations.
194 // if we did, it makes no sense to make a prediction
195 if(dag.getLeaves().length <= 0)
196 {
197 System.out.println("no DAG nodes for " + targetID + " after CC filtering, skip");
198 return;
199 }
200
201 /*
202 * step 2: add annotations to the DAG by iterating over all evidence (= BLAST hits)
203 */
204
205 // once again, iterate over all BLAST hits
206 for(BlastHit b : blastHitsTmp)
207 {
208 // iterate over all GO terms of the current hit
209 for(String s: b.getGoTerms())
210 {
211 //b.activateOntologySupport(relations.getType("GO:"+s));
212
213 // attach to corresponding nodes in the DAG
214 DAGNode n = null;
215 if((n = dag.getDAGNode("GO:" + s)) != null)
216 {
217 n.addHit(b);
218 // update which GO ontologies are supported by the hit, do only those that weren't filtered before
219
220 String r = relations.getType("GO:"+s);
221 if(r == null) // TODO: remove me
222 System.err.println("error! invalid: GO:"+s + " for target " + this.targetID);
223
224 b.activateOntologySupport(r);
225
226 // also add evidence to all "ancestors" in the DAG
227 for(String ancestor: dag.getAncestors("GO:"+s))
228 dag.getDAGNode(ancestor).addHit(b); // here no additional "GO:" is necessary because the getAncestors() method already returns correct IDs
229 }
230 }
231
232 }
233
234 /*
235 * step 3: calculate normalization values
236 */
237 double[] eValueSum = new double[NUM_ONTOLOGIES];
238 double[] eValueSumSquared = new double[NUM_ONTOLOGIES];
239
240 double[] eValueSumLog = new double[NUM_ONTOLOGIES];
241 double[] eValueSumLogSquared = new double[NUM_ONTOLOGIES];
242
243 double[] bitScoreSum = new double[NUM_ONTOLOGIES];
244 double[] bitScoreSumSquared = new double[NUM_ONTOLOGIES];
245
246 int[] unweightedSum = new int[NUM_ONTOLOGIES];
247
248 for(BlastHit b: blastHitsTmp)
249 {
250 //double exponent = -Math.log(limitRange(b.getEValue()));
251 double exponent = getExponent(b.getEValue());
252 //System.out.println(exponent);
253 double exponentLog = Math.log(exponent);
254
255 for(int i=0; i<NUM_ONTOLOGIES; i++)
256 {
257 if(b.supports(i))
258 {
259 unweightedSum[i]++;
260
261 eValueSum[i] += exponent;
262 eValueSumSquared[i] += exponent*exponent;
263
264 eValueSumLog[i] += exponentLog;
265 eValueSumLogSquared[i] += exponentLog*exponentLog;
266
267 bitScoreSum[i] += b.getBitScore();
268 bitScoreSumSquared[i] += b.getBitScore();
269 }
270 }
271 }
272
273 /*
274 * step 4: score all nodes in the DAG
275 */
276 naiveWriter.write(">" + targetID + newline);
277 for(String s: dag.getDAGNodes().keySet())
278 {
279 DAGNode d = dag.getDAGNodes().get(s);
280 double eValueNom = 0, eValueLogNom = 0, bitScoreNom = 0;
281 int unweightedNom = 0;
282
283 for(BlastHit b: d.getSupportingHits())
284 {
285 unweightedNom++;
286
287 //double exponent = -Math.log(limitRange(b.getEValue()));
288 double exponent = getExponent(b.getEValue());
289
290 eValueNom += exponent;
291 eValueLogNom += Math.log(exponent);
292 bitScoreNom += b.getBitScore();
293 }
294
295 int index = ontologyToIndex(relations.getType(s));
296 // System.out.println(index + " -> " + eValueSum[index]);
297 // System.out.print(index);
298
299 d.setUnweightedSCore((double)unweightedNom / (unweightedSum[index] > 0 ? unweightedSum[index] : 1));
300
301 d.seteValueScore(eValueNom / (eValueSum[index] > 1 ? eValueSum[index] : 1));
302 // d.seteValueSquaredScore(eValueNom / (eValueSumSquared[index] > 1 ? eValueSumSquared[index] : 1));
303
304 d.seteValueLogScore(eValueLogNom / (eValueSumLog[index] > 1 ? eValueSumLog[index] : 1));
305 // d.seteValueLogSquaredScore(eValueLogNom / (eValueSumLogSquared[index] > 1 ? eValueSumLogSquared[index] : 1));
306
307 d.setBitScoreScore(bitScoreNom / (bitScoreSum[index] > 1 ? bitScoreSum[index] : 1));
308 // d.setBitScoreSquaredScore(bitScoreNom / (bitScoreSumSquared[index] > 1 ? bitScoreSumSquared[index] : 1));
309
310
311 naiveWriter.write(s + tab + indexToOntology(index) + tab + Tools.round(d.getUnweightedScore()) + tab + Tools.round(d.geteValueScore()) + tab + Tools.round(d.geteValueLogScore()));
312 if(distribution != null)
313 naiveWriter.write(tab + Tools.round(d.getUnweightedScore() * quantile) + tab + Tools.round(d.geteValueScore() * quantile) + tab + Tools.round(d.geteValueLogScore() * quantile));
314
315 naiveWriter.write(newline);
316
317 // System.out.println(s + ": " + d.geteValueScore() + "\t" + "\t" + d.getUnweightedScore() + "\t" + relations.getType(s) + "\t" + eValueSum[index]);
318 // ontologies
319 }
320 naiveWriter.write("//" + newline); // + Character.LINE_SEPARATOR);
321
322 // TODO : 1 - score?
323 // TODO: unweighted kNN
324 // TODO: bitscore macht keinen sinn da direkt abhängig von E-value...http://www.ncbi.nlm.nih.gov/BLAST/tutorial/Altschul-1.html
325
326 /*
327 * step 5: score leaves and output
328 */
329 // System.out.println("biological_process: " + unweightedSum[BIOLOGICAL_PROCESS] + ", " + eValueSum[BIOLOGICAL_PROCESS]);
330 // System.out.println("molecular_function: " + unweightedSum[MOLECULAR_FUNCTION] + ", " + eValueSum[MOLECULAR_FUNCTION]);
331 // System.out.println("cellular_component: " + unweightedSum[CELLULAR_COMPONENT] + ", " + eValueSum[CELLULAR_COMPONENT]);
332
333 leafWriter.write(">" + targetID + newline);
334 for(String l: dag.getLeaves())
335 {
336 DAGNode currentNode = dag.getDAGNodes().get(l);
337
338 double leafScoreEValue = currentNode.geteValueScore();
339 double leafScoreEValueLog = currentNode.geteValueLogScore();
340 double leafScoreUnweighted = currentNode.getUnweightedScore();
341
342 for(String m: dag.getAncestors(l))
343 {
344 leafScoreEValue += dag.getDAGNodes().get(m).geteValueScore();
345 leafScoreEValueLog += dag.getDAGNodes().get(m).geteValueLogScore();
346 leafScoreUnweighted += dag.getDAGNodes().get(m).getUnweightedScore();
347 }
348
349 int N = dag.getAncestors(l).length + 1;
350 currentNode.setLeafScoreEValue(leafScoreEValue / N);
351 currentNode.setLeafScoreEValueLog(leafScoreEValueLog / N);
352 currentNode.setLeafScoreUnweighted(leafScoreUnweighted / N);
353
354 // System.out.println("->" + l + " " + dag.getDAGNodes().get(l).getSupportingHits().size() + " " + dag.getDAGNodes().get(l).geteValueScore() + " " + dag.getDAGNodes().get(l).getLeafScoreEValue() + " " + relations.getType(l));
355 leafWriter.write(l + tab + indexToOntology(ontologyToIndex(relations.getType(l))) + tab + Tools.round(currentNode.getLeafScoreUnweighted()) + tab + Tools.round(currentNode.getLeafScoreEValue()) + tab + Tools.round(currentNode.getLeafScoreEValueLog()));
356 if(distribution != null)
357 leafWriter.write(tab + Tools.round(currentNode.getLeafScoreUnweighted() * quantile) + tab + Tools.round(currentNode.getLeafScoreEValue() * quantile) + tab + Tools.round(currentNode.getLeafScoreEValueLog() * quantile));
358
359 leafWriter.write(newline);
360 }
361 leafWriter.write("//" + newline);
362 // if(relations.getType(l).equals("biological_process"))
363 // ; //continue;
364 //
365 // System.out.println("->" + l + " " + dag.getDAGNodes().get(l).getSupportingHits().size() + " " + dag.getDAGNodes().get(l).geteValueScore() + " " + relations.getType(l));
366 // System.out.print("\t");
367 // for(String m: dag.getAncestors(l))
368 // {
369 // //System.out.print(" | " + m + "="+dag.getDAGNodes().get(m).geteValueScore());
370 // System.out.print(" | " + m + "="+dag.getDAGNodes().get(m).getSupportingHits().size());
371 // }
372 // System.out.println();
373 // }
374
375 }
376
377
378 }