View Javadoc

1   /*--------------------------------------------------------------------------
2    *  Copyright 2010 utgenome.org
3    *
4    *  Licensed under the Apache License, Version 2.0 (the "License");
5    *  you may not use this file except in compliance with the License.
6    *  You may obtain a copy of the License at
7    *
8    *     http://www.apache.org/licenses/LICENSE-2.0
9    *
10   *  Unless required by applicable law or agreed to in writing, software
11   *  distributed under the License is distributed on an "AS IS" BASIS,
12   *  WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
13   *  See the License for the specific language governing permissions and
14   *  limitations under the License.
15   *--------------------------------------------------------------------------*/
16  //--------------------------------------
17  // utgb-core Project
18  //
19  // ReadDepth.java
20  // Since: 2010/12/09
21  //
22  //--------------------------------------
23  package org.utgenome.util;
24  
25  import java.util.Iterator;
26  import java.util.PriorityQueue;
27  
28  import org.utgenome.gwt.utgb.client.bio.Interval;
29  import org.utgenome.gwt.utgb.client.bio.OnGenome;
30  import org.utgenome.gwt.utgb.client.canvas.IntervalTree;
31  import org.xerial.util.log.Logger;
32  
33  /**
34   * Read depth computation in O(2N) time.
35   * 
36   * @author leo
37   * 
38   */
39  public class ReadDepth {
40  
41  	private static Logger _logger = Logger.getLogger(ReadDepth.class);
42  
43  	private int startCursor = 0;
44  	private int readCount = 0;
45  	private IntervalTree<Interval> intervals = new IntervalTree<Interval>();
46  
47  	private PriorityQueue<Integer> boundary = new PriorityQueue<Integer>();
48  	private int currentDepth = 0;
49  
50  	private final DepthOutput out;
51  
52  	protected ReadDepth(DepthOutput out) {
53  		this.out = out;
54  	}
55  
56  	public static interface DepthOutput {
57  		public void reportDepth(String chr, int start, int end, int depth) throws Exception;
58  	}
59  
60  	/**
61  	 * Compute the read depth of the input read set. The read set must be sorted by start order.
62  	 * 
63  	 * @param cursor
64  	 * @param out
65  	 * @throws Exception
66  	 */
67  	public static void compute(String chr, Iterator<OnGenome> cursor, DepthOutput out) throws Exception {
68  		new ReadDepth(out).computeDepth(chr, cursor);
69  	}
70  
71  	protected void computeDepth(String chr, Iterator<OnGenome> cursor) throws Exception {
72  
73  		for (; cursor.hasNext();) {
74  			OnGenome read = cursor.next();
75  			readCount++;
76  
77  			if (_logger.isDebugEnabled() && readCount > 0 && (readCount % 10000) == 0) {
78  				_logger.debug(String.format("processed %d reads", readCount));
79  			}
80  
81  			int start = read.getStart();
82  			int end = read.getEnd();
83  			boundary.add(end);
84  
85  			for (; !boundary.isEmpty();) {
86  				int readEnd = boundary.peek();
87  				if (readEnd > start)
88  					break;
89  
90  				reportDepth(chr, startCursor, readEnd, currentDepth);
91  				currentDepth--;
92  				startCursor = readEnd;
93  				boundary.poll();
94  			}
95  
96  			if (startCursor < start)
97  				reportDepth(chr, startCursor, start, currentDepth);
98  			startCursor = start;
99  			currentDepth++;
100 		}
101 
102 		for (; !boundary.isEmpty();) {
103 			int readEnd = boundary.peek();
104 			reportDepth(chr, startCursor, readEnd, currentDepth);
105 			currentDepth--;
106 			startCursor = readEnd;
107 			boundary.poll();
108 		}
109 
110 	}
111 
112 	private void reportDepth(String chr, int start, int end, int depth) throws Exception {
113 		out.reportDepth(chr, start, end, depth);
114 	}
115 
116 }