Bin.java - code915 - My code for INSERM UMR915

Source path: svn/ trunk/ core/ src/ java/ fr/ inserm/ umr915/ core/ bio/ ucsc/ Bin.java

‹r107

r463

package fr.inserm.umr915.core.bio.ucsc;

import java.util.HashSet;
import java.util.Iterator;
import java.util.Set;


/**
 * inspired from Kent, et. al. Genome Research 2002.12:996-1006
 * http://genome.cshlp.org/content/12/6/996.full
 * http://genomewiki.ucsc.edu/index.php/Bin_indexing_system 
 * Bin
 */
public abstract class Bin
	{
	
	

	/** original Jim Kent's implementation */
	public static int binFromRangeStandard(int start, int end)
	
		{
		final int binOffsets[] =
			{
			512+64+8+1,
			64+8+1,
			8+1,
			1,
			0};
		
		
		/** How much to shift to get to finest bin. */
		final int _binFirstShift=17; 
		/** How much to shift to get to next larger bin.*/
		final int _binNextShift=3; 

		int startBin = start;
		int endBin = end-1;
		
		
		//System.out.println("1 startBin="+startBin+" endBin="+endBin);
		
		startBin >>= _binFirstShift;
		endBin >>= _binFirstShift;
		
		
		//System.out.println("2 startBin="+startBin+" endBin="+endBin);
		
		for(int binOffset : binOffsets)
		    {
		    if (startBin == endBin)
		    	{
		        return binOffset + startBin;
		    	}
		    startBin >>= _binNextShift;
		    endBin >>= _binNextShift;
		   // System.out.println("3 startBin="+startBin+" endBin="+endBin+" binOffset:"+binOffset);
		    }
		throw new IllegalArgumentException("start "+start+", end "+ end+" out of range in findBin (max is 512M)");
		}
	
	/** to be implemented */
	/*private class BinIterator
		implements Iterator<Integer>
		{
		private int chromStart;
		private int chromEnd;
		private int level=0;
	
		@Override
		public Integer next()
			{
			return null;
			}
		@Override
		public boolean hasNext()
			{
			
			return false;
			}
		
		@Override
		public void remove()
			{
			throw new UnsupportedOperationException();
			}
		}*/
	
	private Set<Integer> collectBins(
			final int chromStart,
			final int chromEnd,
			int binId,
			int level,
			int binRowStart,
			int rowIndex,
			int binRowCount,
			int genomicPos,
			int genomicLength,
			Set<Integer> set
			)
			{
			set.add(binId);
			if(level>=getMaxLevel()) return set;
			
			int childLength=genomicLength/getChildrenCount();
			int childBinRowCount=binRowCount*getChildrenCount();
			int childRowBinStart=binRowStart+binRowCount;
			int firstChildIndex=rowIndex*getChildrenCount();
			int firstChildBin=childRowBinStart+firstChildIndex;
			for(int i=0;i< getChildrenCount();++i)
				{
				int childStart=genomicPos+i*childLength;
				
				if( chromStart>(childStart+childLength) ||
					chromEnd<childStart )
					{
					continue;
					}
				collectBins(
					chromStart,
					chromEnd,
					firstChildBin+i,
					level+1,
					childRowBinStart,
					firstChildIndex+i,
					childBinRowCount,
					childStart,
					childLength,
					set
					);
				}
			return set;
			}
	
	
	private int calcBin(
		final int chromStart,
		final int chromEnd,
		int binId,
		int level,
		int binRowStart,
		int rowIndex,
		int binRowCount,
		int genomicPos,
		int genomicLength
		)
		{

		if( 
			chromStart>=genomicPos &&
			chromEnd<= (genomicPos+genomicLength))
			{
			if(level>=getMaxLevel()) return binId;
			
			int childLength=genomicLength/getChildrenCount();
			int childBinRowCount=binRowCount*getChildrenCount();
			int childRowBinStart=binRowStart+binRowCount;
			int firstChildIndex=rowIndex*getChildrenCount();
			int firstChildBin=childRowBinStart+firstChildIndex;
			for(int i=0;i< getChildrenCount();++i)
				{
				//System.out.println("i:"+i+"=>"+(firstChildBin+i));
				//System.out.println(" "+(genomicPos+i*childLength)+" <=" +chromStart+" < "+chromEnd+"<"+(genomicPos+(i+1)*childLength));
				int n= calcBin(
						chromStart,
						chromEnd,
						firstChildBin+i,
						level+1,
						childRowBinStart,
						firstChildIndex+i,
						childBinRowCount,
						genomicPos+i*childLength,
						childLength
						);
				if(n!=-1)
					{
					//System.out.println("returning n="+n);
					return n;
					}
				}
			return binId;
			}
		
		return -1;
		}
	
	/** length for level 0 */
	protected abstract int getMaxGenomicLengthLevel();
	/** maximum level in Jim Kent's algorithm */
	protected abstract int getMaxLevel();
	/** how many children for one node ? */
	protected abstract int getChildrenCount();
		
	
	/** Given start,end in chromosome coordinates assign it
	 * a bin.   There's a bin for each 128k segment, for each
	 * 1M segment, for each 8M segment, for each 64M segment,
	 * and for each chromosome (which is assumed to be less than
	 * 512M.)  A range goes into the smallest bin it will fit in. */
	public int getBin(int chromStart,int chromEnd)
		{
		int genomicLength=getMaxGenomicLengthLevel();
		return calcBin(chromStart,chromEnd,0,0,0,0,1,0,genomicLength);
		}
	
	/** returns all the bin-ids overlapping the given range */
	public Set<Integer> getBins(int chromStart,int chromEnd)
		{
		int genomicLength=getMaxGenomicLengthLevel();
		return collectBins(chromStart,chromEnd,0,0,0,0,1,0,genomicLength,new HashSet<Integer>());
		}
	
	
	public Iterator<Integer> getIterator(int chromStart,int chromEnd)
		{
		//TODO , use an iterator rather than calling getBins
		return getBins(chromStart,chromEnd).iterator();
		}
	
	
	/** default used by ucsc level 0: 512Mo */
	public final static Bin Ucsc512=new Bin()
		{
		@Override
		protected int getChildrenCount()
			{
			return 8;
			}
		
		@Override
		protected int getMaxLevel()
			{
			return 4;
			}
		
		@Override
		protected int getMaxGenomicLengthLevel()
			{
			return 536870912;//2^29
			}
		};
	
	public static void main(String[] args)
		{
		try
			{
			System.out.println(binFromRangeStandard(10003,10004));
			System.out.println(Ucsc512.getBin(10003,10004));
			System.out.print("(");
			for(int i:Ucsc512.getBins(10000,20000))
				{
				System.out.print(i);
				System.out.print(",");
				}
			System.out.println(")");
			/*for(int i=0;false && i< 536870912-1;++i )
				{
				int n1;
				int n2;
				if((n1=Ucsc512.getBin(i,i+1))!=(n2=binFromRangeStandard(i,i+1)))
					{
					System.err.println(i+"\t"+n1+"\t"+n2);
					}
				}*/
			System.out.println("Done.");
			}
		catch (Exception e)
			{
			e.printStackTrace();
			}
		}
	
	}

Show details Hide details

Change log

r110 by plindenbaum.u915 on May 28, 2010 Diff

cont

Go to:

Project members, sign in to write a code review

Older revisions

r107 by plindenbaum.u915 on May 27, 2010 Diff

cont

All revisions of this file

File info

Size: 6107 bytes, 273 lines

View raw file