Suppose we have two random sequences A and B of **L nucleotide** each. What is the probability to observe a common substring (kmer) of at least **k nucleotides** between those two strings ? What I have got so far :

    #param :
    k = 3  #common substring must be of at least 3 nucleotides
    L = length(A) = length(B) = 12  #the two random sequences are 12 nt long
    
    prob_kmer = 1/(4**k)  # 1/64, the probability to observe a particular sequence in a random kmer
    N_prob_kmer = 1 - prob_kmer  # 63/64, the probability to NOT observe a particular sequence in a random kmer
    nb_kmer = L - k + 1 # 10, the number of possible kmer in a sequence of length 12
    nb_comparison = nb_kmer**2 # 100, the number of kmer comparison between the two sequences of length 12

    P = 1 - ((N_prob_kmer)**(nb_comparison)) # 80%, probability to find at least one of the kmer of sequence A matching a kmer of sequence B.
    
Is this correct ? I'm concerned that subsequent k-mer do not have independent sequences (they share some nucleotide since they are overlapping) so the probabilities are not independent either... But I have no idea how to take that into account in my calculation.

Thanks.

I would approach the problem like this:

> 1) Estimate number of unique kmers in each sequence.
> 
> 2) Calculate probability of the sets intersecting.

I'm sure there's a closed-form solution for each, but I don't know them off the top of my head, so here's how I'd do it iteratively:

    public class ProbShared {
    
    	public static void main(String args[]){
    		int k=Integer.parseInt(args[0]);
    		int len1=Integer.parseInt(args[1]);
    		int len2=Integer.parseInt(args[2]);
    
    		System.out.println("Cardinality 1: "+cardinality(k, len1));
    		System.out.println("Cardinality 2: "+cardinality(k, len2));
    		System.out.println("Probability:   "+probIntersect(k, len1, len2));
    		
    	}
    	
    	static int cardinality(int k, int seqLength){
    		double space=Math.pow(4, k);
    		int kmers=seqLength-k+1;
    		double unique=0;
    		for(int i=0; i<kmers; i++){
    			double prob=(space-unique)/space;
    			unique+=prob;
    		}
    		return (int)Math.round(unique);
    	}
    
    	static double probIntersect(int k, int len1, int len2){
    		int card1=cardinality(k, len1);
    		int card2=cardinality(k, len2);
    		double space=Math.pow(4, k);
    		int kmers=len1-k+1;
    		double cumulativeProbUnshared=1;
    		for(int i=0; i<card1; i++){
    			double probShared=card2/space;
    			double probUnshared=1-probShared;
    			space-=probUnshared;
    			cumulativeProbUnshared*=probUnshared;
    		}
    		return 1-cumulativeProbUnshared;
    	}
    	
    }


This does not handle the dangling probability after rounding in the cardinality function, but it could be adjusted to do so.  Sample output:

    C:\temp>java fun.ProbShared 3 10 17
    Cardinality 1: 8
    Cardinality 2: 13
    Probability:   0.8521277771213935

Edit:  As explained below, this does NOT correctly solve the problem of kmers generated from strings (which all overlap); rather, it solves the problem for sets of completely random numbers.  As a result, it gives an overestimate for the probability of two strings sharing kmers by up to ~25% depending on the string length and kmer length.  The reason is that if two strings share one kmer, there is a minimum of a 25% chance that they also share the next kmer, and 6.25% chance that they share the kmer after that, rather than a flat 1/(4^K) chance if the kmers were non-overlapping.  Therefore, if two strings *don't* share a specific kmer, there must be a similarly reduced chance that they don't share the next kmer.  It's probably possible to update the code to be correct given this information.