| 1 |
package pp2.prediction.knn; |
| 2 |
|
| 3 |
import java.util.ArrayList; |
| 4 |
import java.util.Collections; |
| 5 |
import java.util.HashMap; |
| 6 |
import java.util.LinkedList; |
| 7 |
|
| 8 |
/** |
| 9 |
* |
| 10 |
* @author Thomas Hopf |
| 11 |
* |
| 12 |
*/ |
| 13 |
public class kNearestNeighbor { |
| 14 |
|
| 15 |
/* |
| 16 |
* constants for different node scoring methods |
| 17 |
*/ |
| 18 |
public static final int EVAL_UNWEIGHTED = 1; // this is unweighted kNN |
| 19 |
public static final int EVAL_LOG_SCORING = 2; |
| 20 |
public static final int EVAL_LOG_LOG_SCORING = 3; |
| 21 |
//public static final int SEQID_SCORING = 4; |
| 22 |
|
| 23 |
/** |
| 24 |
* limits the range of E-values such that log values are meaningful (i.e., -log(value) is defined and non-negative) |
| 25 |
*/ |
| 26 |
private double limitRange(double value) |
| 27 |
{ |
| 28 |
return Math.max(1E-308, Math.min(value, 1)); |
| 29 |
} |
| 30 |
|
| 31 |
/** |
| 32 |
* |
| 33 |
* @param blastHits file like "go_test_output". must already contain fully added GO paths! |
| 34 |
* @param scoringMethod determines type of sequence weighting, specified by one of the constants EVAL_* |
| 35 |
* @param useEValueThreshold determines whether conventional kNN or a fixed E-Value threshold is used to include BLAST hits |
| 36 |
* @param eValueThreshold if useEvalueThreshold == true, then all hits with an E-Value below this parameter are included |
| 37 |
* @param k if conventional kNN is used, this determines the fixed number of neighbors to use, if there are enough |
| 38 |
*/ |
| 39 |
public ArrayList<GoNode> predictFunction(BlastResultList blastHits, int scoringMethod, boolean useEValueThreshold, float eValueThreshold, int k) |
| 40 |
{ |
| 41 |
// all GO term nodes |
| 42 |
HashMap<String, GoNode> nodes = new HashMap<String, GoNode>(); |
| 43 |
|
| 44 |
// reliability values of each BLAST hit (e.g. E-Value per hit) |
| 45 |
LinkedList<Double> normalizationValues = new LinkedList<Double>(); |
| 46 |
int i = 0; |
| 47 |
|
| 48 |
/* |
| 49 |
* iterate over all hits in the BLAST file |
| 50 |
*/ |
| 51 |
for(BlastHit h: blastHits.getHits()) |
| 52 |
{ |
| 53 |
// only consider first k hits if doing conventional kNN |
| 54 |
if(!useEValueThreshold && i>=k) |
| 55 |
break; |
| 56 |
|
| 57 |
// if doing "E-Value threshold"-kNN, skip current hit (for safety: not assuming the blast hit list is sorted by E-value) |
| 58 |
if(useEValueThreshold && h.getEValue() > eValueThreshold) |
| 59 |
continue; |
| 60 |
|
| 61 |
// iterate over all go terms of the current hit |
| 62 |
for(String goTerm: h.getGoTerms()) |
| 63 |
{ |
| 64 |
// check if we already had that GO term, otherwise create a new GO term node. |
| 65 |
// in both cases add the index and the reliability score (e.g. E-value) of the blast hit that supports the node |
| 66 |
if(nodes.containsKey(goTerm)){ |
| 67 |
nodes.get(goTerm).addHit(i, h.getEValue()); |
| 68 |
} else { |
| 69 |
nodes.put(goTerm, new GoNode(goTerm, i, h.getEValue())); |
| 70 |
} |
| 71 |
} |
| 72 |
|
| 73 |
// add current hit to scoring function normalization factor list |
| 74 |
normalizationValues.add(h.getEValue()); |
| 75 |
|
| 76 |
i++; |
| 77 |
} |
| 78 |
|
| 79 |
/* |
| 80 |
* calculate normalization factor |
| 81 |
*/ |
| 82 |
double normalizationFactor = 0; |
| 83 |
for(double value: normalizationValues) |
| 84 |
{ |
| 85 |
value = limitRange(value); |
| 86 |
|
| 87 |
switch(scoringMethod) { |
| 88 |
case EVAL_UNWEIGHTED: |
| 89 |
normalizationFactor += 1; |
| 90 |
break; |
| 91 |
case EVAL_LOG_SCORING: |
| 92 |
normalizationFactor += -Math.log(value); |
| 93 |
break; |
| 94 |
case EVAL_LOG_LOG_SCORING: |
| 95 |
normalizationFactor += Math.log((-Math.log(value))); |
| 96 |
break; |
| 97 |
default: break; |
| 98 |
} |
| 99 |
} |
| 100 |
|
| 101 |
// slight hack for safety: ensure normalization factor is nonzero |
| 102 |
if(normalizationFactor <= 0.01) |
| 103 |
normalizationFactor = 1; |
| 104 |
|
| 105 |
//System.out.println("normalization factor: " + normalizationFactor); |
| 106 |
|
| 107 |
|
| 108 |
/* |
| 109 |
* iterate over all nodes to calculate their individual score |
| 110 |
*/ |
| 111 |
for(GoNode node: nodes.values()) |
| 112 |
{ |
| 113 |
double score = 0; |
| 114 |
|
| 115 |
for(double value: node.getReliabilities()) |
| 116 |
{ |
| 117 |
value = limitRange(value); |
| 118 |
|
| 119 |
switch(scoringMethod) { |
| 120 |
case EVAL_UNWEIGHTED: |
| 121 |
score += 1; |
| 122 |
break; |
| 123 |
case EVAL_LOG_SCORING: |
| 124 |
score += -Math.log(value); |
| 125 |
break; |
| 126 |
case EVAL_LOG_LOG_SCORING: |
| 127 |
score += Math.log((-Math.log(value))); |
| 128 |
break; |
| 129 |
default: break; |
| 130 |
} |
| 131 |
} |
| 132 |
node.setScore(score / normalizationFactor); |
| 133 |
|
| 134 |
//System.out.println(node.getGoTerm() + ":" + node.getReliabilities().size() + "->" + node.getScore()); |
| 135 |
} |
| 136 |
|
| 137 |
ArrayList<GoNode> resultNodeList = new ArrayList<GoNode>(nodes.values()); |
| 138 |
Collections.sort(resultNodeList); |
| 139 |
return resultNodeList; |
| 140 |
} |
| 141 |
|
| 142 |
|
| 143 |
/** |
| 144 |
* @param args |
| 145 |
*/ |
| 146 |
public static void main(String[] args) throws Exception { |
| 147 |
// nimmt an, dass go_test_output aufsteigend nach E-values sortiert ist, und bereits die vollen GO-pfade enthält |
| 148 |
BlastResultList brl = new BlastResultList("examples/go_test_output"); |
| 149 |
|
| 150 |
kNearestNeighbor knn = new kNearestNeighbor(); |
| 151 |
|
| 152 |
System.out.println("#GOterm\t\tnum seq\tscore"); |
| 153 |
for(GoNode g: knn.predictFunction(brl, kNearestNeighbor.EVAL_LOG_LOG_SCORING, true, 1, 9)) |
| 154 |
System.out.println(g.getGoTerm() + "\t" + g.getReliabilities().size() + "\t" + g.getScore()); |
| 155 |
|
| 156 |
// TODO: die result-liste kann noch nodes mit score 0 enthalten! |
| 157 |
// TODO: kommandozeilenparameter, output file schreiben etc. |
| 158 |
|
| 159 |
} |
| 160 |
|
| 161 |
} |