| 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 |
} |