Skip to content

Instantly share code, notes, and snippets.

@lindenb

lindenb/debruijn.js

Last active March 22, 2021 22:58
Show Gist options
  • Save lindenb/abd63a6a6655fecbe0a9daf384eacbfe to your computer and use it in GitHub Desktop.
Save lindenb/abd63a6a6655fecbe0a9daf384eacbfe to your computer and use it in GitHub Desktop.
Download ZIP
de bruijn graph in javascript
Raw
debruijn.js
function GraphNode(kmer) {
this.id = GraphNode.ID++;
this.kmer=kmer;
this.rightNodes = [];
}
GraphNode.ID=0;
/* insert new node on the right */
GraphNode.prototype.append = function(nodeR) {
var i,n;
for(i=0;i< this.rightNodes.length;++i) {
n= this.rightNodes[i];
// nodeR already inserted
if(n.kmer == nodeR.kmer) return;
}
this.rightNodes.push(nodeR);
}
function DeBruijnGraph(kmerSize) {
this.kmer2nodes = {};
this.kmerSize=kmerSize;
}
/** create a new node in the graph */
DeBruijnGraph.prototype.makeNode = function(kmer) {
var n= this.kmer2nodes[kmer];
/* already in graph */
if(n!=null) return n;
/* create new and insert */
n = new GraphNode(kmer);
this.kmer2nodes[kmer] = n;
return n;
}
/** reverse complement DNA seq */
DeBruijnGraph.prototype.reverseComplement = function(s) {
var i, o = '';
for ( i = s.length - 1; i >= 0; i--)
{
switch(s[i]) {
case 'A': o+='T'; break;
case 'T': o+='A'; break;
case 'G': o+='C'; break;
case 'C': o+='G'; break;
default: o+='N';break;
}
}
return o;
}
/* insert new read in the graph */
DeBruijnGraph.prototype.insert = function(read) {
var i,strand;
for(i=0;i + (this.kmerSize+1) <= read.length;++i) {
for(strand=0;strand<2;++strand) {
var subread = read.substring(i,i+(this.kmerSize+1));
/* get reverse complement ? */
if(strand==1) subread= this.reverseComplement(subread);
/* left kmer */
var kmerL = subread.substring(0,this.kmerSize);
/* left node */
var nodeL = this.makeNode(kmerL);
/* right kmer */
var kmerR = subread.substring(1, 1+ this.kmerSize);
/* right node */
var nodeR = this.makeNode(kmerR);
/** append right to left */
nodeL.append(nodeR);
}// end loop over strand
} // end loop over sequence
}//end 'insert'
function execute() {
var graph = new DeBruijnGraph(7);
var i,k,n= document.getElementById("reads");
var seqs=n.value.split(/[ \n]/);
for(i=0;i< seqs.length;++i) {
if(seqs[i].length==0) continue;
graph.insert(seqs[i]);
}
n= document.getElementById("out");
while(n.firstChild) n.removeChild(n.firstChild);
var dot="digraph G {\n";
for(k in graph.kmer2nodes) {
var kn = graph.kmer2nodes[k];
dot+= "n"+kn.id+"[label=\""+ (kn.rightNodes.length==0?k:k[0]) + "\"];\n";
for(var r in kn.rightNodes) {
dot+= "n"+kn.id+" -> n"+ kn.rightNodes[r].id +";\n";
}
}
dot+="}\n";
n.appendChild( document.createTextNode(dot) );
}
Raw
index.html
<html>
<head>
<meta http-equiv="Content-Type" content="text/html; charset=UTF-8"/>
<script src="debruijn.js"></script>
<body>
Reads:<br/>
<textarea id="reads" cols="100" rows="5">
CATTAGGGAGCTGTGGACCCTG
CTGTGGACCCTGCAGCCTGGCTGTTG
GGTCCACAGCTCCC
</textarea><br/>
<button onclick="execute()">RUN</button><br/>
Output:
<pre id="out"></pre>
</body>
</html>
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment