Brunobkr/llama.cpp_AlgMor24_github

1/**2 *   Needleman-Wunsch algorithm is an procedure to compute the optimal global alignment of two string3 *   sequences by S.B.Needleman and C.D.Wunsch (1970).4 *5 *   Aside from the inputs, you can assign the scores for,6 *   - Match: The two characters at the current index are same.7 *   - Mismatch: The two characters at the current index are different.8 *   - Insertion/Deletion(gaps): The best alignment involves one letter aligning to a gap in the other string.9 */10 11class NeedlemanWunsch {12    constructor(sequence1, sequence2, match_score = 1, mismatch_penalty = -1, gap_penalty = -1) {13        this.sequence1 = sequence1;14        this.sequence2 = sequence2;15        this.match_score = match_score;16        this.mismatch_penalty = mismatch_penalty;17        this.gap_penalty = gap_penalty;18 19        // Just the remove redundancy20        this.iMax = sequence1.length + 1;21        this.jMax = sequence2.length + 1;22 23        // Grid matrix of scores24        this.grid = new Array(this.iMax);25        for(let i = 0; i < this.iMax; i++){26            this.grid[i] = new Array(this.jMax );27 28            for(let j = 0; j < this.jMax ; j++)29                this.grid[i][j] = 0;30        }31 32        // Traceback matrix (2D array, each cell is an array of boolean values for [`Diag`, `Up`, `Left`] positions)33        this.tracebackGrid = new Array(this.iMax);34        for(let i = 0; i < this.iMax; i++) {35            this.tracebackGrid[i] = new Array(this.jMax);36 37            for(let j = 0; j < this.jMax ; j++)38                this.tracebackGrid[i][j] = [null, null, null];39        }40 41        // The aligned sequences (return multiple possibilities)42        this.alignments = [];43 44        // Final alignment score45        this.score = -1;46 47        // Calculate scores and tracebacks48        this.computeGrids();49    }50 51    getScore(){52        return this.score;53    }54 55    getAlignments(){56        return this.alignments;57    }58 59    // Main dynamic programming procedure60    computeGrids(){61        // Fill in the first row62        for (let j = 1; j < this.jMax; j++) {63            this.grid[0][j] = this.grid[0][j-1] + this.gap_penalty;64            this.tracebackGrid[0][j] = [false, false, true];65        }66 67        // Fill in the first column68        for (let i = 1; i < this.iMax; i++) {69            this.grid[i][0] = this.grid[i-1][0] + this.gap_penalty;70            this.tracebackGrid[i][0] = [false, true, false];71        }72 73        // Fill the rest of the grid74        for(let i = 1; i < this.iMax; i++){75            for(let j = 1; j < this.jMax; j++){76                // Find the max score(s) among [`Diag`, `Up`, `Left`]77                let diag;78                if(this.sequence1[i-1] === this.sequence2[j-1])79                    diag = this.grid[i-1][j-1] + this.match_score;80                else81                    diag = this.grid[i-1][j-1] + this.mismatch_penalty;82 83                let up = this.grid[i-1][j] + this.gap_penalty;84                let left = this.grid[i][j-1] + this.gap_penalty;85 86                // If there exists multiple max values, capture them for multiple paths87                let maxOf = [diag,up,left];88                let indices = this.arrayAllMaxIndexes(maxOf);89 90                // Update Grids91                this.grid[i][j] = maxOf[indices[0]];92                this.tracebackGrid[i][j] = [indices.includes(0), indices.includes(1), indices.includes(2)];93            }94        }95 96        // Update alignment score97        this.score = this.grid[this.iMax-1][this.jMax-1];98    }99 100    // Gets all possible valid sequence combinations101    alignmentTraceback(){102        let inProcessAlignments = [];103 104        inProcessAlignments.push({ pos: [this.sequence1.length, this.sequence2.length],105            seq1: "",106            seq2: ""107        });108 109        while(inProcessAlignments[0]){110            let current = inProcessAlignments[0];111            let directions = this.tracebackGrid[current.pos[0]][current.pos[1]];112 113            if(directions[0]){114                inProcessAlignments.push({ pos: [current.pos[0]-1, current.pos[1]-1],115                    seq1: (this.sequence1[current.pos[0]-1] + current.seq1),116                    seq2: (this.sequence2[current.pos[1]-1] + current.seq2)117                });118            }119            if(directions[1]){120                inProcessAlignments.push({ pos: [current.pos[0]-1, current.pos[1]],121                    seq1: this.sequence1[current.pos[0]-1] + current.seq1,122                    seq2: '-' + current.seq2123                });124            }125            if(directions[2]){126                inProcessAlignments.push({ pos: [current.pos[0], current.pos[1]-1],127                    seq1:'-' + current.seq1,128                    seq2: this.sequence2[current.pos[1]-1] + current.seq2129                });130            }131 132            if(current.pos[0] === 0 && current.pos[1] === 0)133                this.alignments.push({sequence1 : current.seq1,134                    sequence2: current.seq2135                });136 137            inProcessAlignments.shift();138        }139 140        return this.alignments;141    }142 143    // Helper Functions144 145    getAllIndexes(arr, val) {146        let indexes = [], i = -1;147        while ((i = arr.indexOf(val, i+1)) !== -1){148            indexes.push(i);149        }150        return indexes;151    }152 153    arrayAllMaxIndexes(array){154        return this.getAllIndexes(array, Math.max.apply(null, array));155    }156}157 158module.exports = NeedlemanWunsch;