Debian Codegraph @

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

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