Computer-facilitated parallel information alignment and analysis

A method, implemented at least in part by a computing system, the method comprising:

• initializing in a parallel memory of the computing system a 2-D matrix wherein respective of the columns in the 2-D matrix store characters corresponding to an anti-diagonal of a Smith-Waterman (S-W) matrix formed from sequences S1 and S2 representing information sequences comprising a string of at least two characters, the initializing comprising shifting, in parallel, data from a copy of the S2 sequence stored in the parallel memory to columns of the 2-D matrix such that the columns store anti-diagonals of the S-W matrix, the contents of the copy of the S2 sequence being shifted between shiftings of the copy of the S2 sequence into the columns of the 2-D matrix;
• computing, in parallel, deletion values (D values), insertion values (I values), and match values (C values) for the 2-D matrix;
• and
• conducting a traceback analysis of the 2-D matrix starting from a highest computed C value, to produce an alignment between characters in the sequences S1 and S2.

A computer system comprising:

• a plurality of processing elements (PEs) respective of the plurality of processing elements having local memory, the local memories collectively defining a parallel memory;
• a PE interconnection network connecting the plurality of processing elements;
• one or more computer-readable storage media storing instruction for causing the computer system to execute a method, the method comprising:
• initializing in the parallel memory a 2-D matrix wherein respective of the columns in the 2-D matrix stores characters corresponding to an anti-diagonal of a Smith-Waterman (S-W) matrix formed from sequences S1 and S2, respective of the sequences S1 and S2 representing information sequences comprising strings of at least two characters;
• using the plurality of PEs, computing, in parallel, deletion values (D values), insertion values (I values), and match values (C values) for the 2-D matrix;
• conducting a traceback of the 2-D matrix from a highest computed C value, to produce a first alignment between characters in the sequences S1 and S2;
• masking out characters in the sequences S1 and S2 based on the first alignment;
• repeating the initializing, the computing and the conducting traceback at least one time, to produce at least one additional alignment between sequences S1 and S2 that does not overlap or intersect with the first alignment;
• and
• masking out the characters of the sequences S1 and S2 included in additional subsequent alignments to one or more excluded characters prior to repeating the computing and the conducting a traceback.

A method, implemented at least in part by a computing system, the method comprising:

• computing, in parallel, deletion values (D values), insertion values (I values) and match values (C values) for a plurality of blocks of a 2-D matrix storing characters corresponding to portions of anti-diagonal of a Smith-Waterman (S-W) matrix formed from sequences S1 and S2, respective of the sequences S1 and S2 representing information sequences comprising strings of at least two characters;
• wherein the blocks are arranged in a 2-D block matrix;
• wherein the computing in parallel is performed by one or more processing cores of a computing system, the one or more processing cores arranged logically adjacent to one another in a left-to-right manner;
• wherein respective of the one or more processing cores are configured to compute in parallel the D, I and C values for one block at a time, and, upon completing the computing for one of the blocks, passing the computed D, I and C values for an upper-most column of the block processed by the respective core to the processor to the respective processor's logical right for use in processing the lowest column in the block stored in the processor to the respective processor's logical right, and using the computed values for the lowest row of the respective core for processing its upper row when processing the next block;
• wherein respective of the blocks successively process blocks belonging to a column of the 2-D matrix in a top-to-bottom manner;
• and
• wherein the blocks are processed one anti-diagonal of the 2-D block matrix at a time in order from the upper left to the lower right of the 2-D block matrix, the blocks belonging to an anti-diagonal of the 2-D block matrix being processed simultaneously by the one or more processing cores;
• and
• conducting a traceback analysis of the 2-D matrix starting from a highest computed C value, to produce a first alignment between characters in the sequences S1 and S2.

A computing system comprising:

• a means for computing, in parallel, deletion values (D values), insertion values (I values), and match values (C values) for a 2-D matrix stored in a parallel memory of the computing system, respective of the columns in the 2-D matrix storing characters corresponding to an anti-diagonal of a Smith-Waterman (S-W) matrix formed from sequences S1 and S2, respective of the sequences S1 and S2 representing information sequences comprising strings of at least two characters;
• a means for conducting a traceback of the 2-D matrix starting from a highest computed C value, to produce a first alignment between characters in the sequences S1 and S2;
• a means for masking out one or more characters in the sequences S1 and S2 based on the first alignment;
• and
• a means for repeating the computing and the conducting a traceback at least one time, to produce at least one additional alignment between the sequences S1 and S2, the first alignment and the at least one additional alignment being non-overlapping, non-intersecting alignments.

A method, implemented at least in part by a computing system, the method comprising:

• initializing in a parallel memory of the computing system a 2-D matrix wherein respective of the columns in the 2-D matrix store characters corresponding to an anti-diagonal of a Smith-Waterman (S-W) matrix formed from sequences S1 and S2 representing information sequences comprising a string of at least two characters, the initializing comprising shifting, in parallel, data from a copy of the S2 sequence stored in the parallel memory to columns of the 2-D matrix such that the columns store anti-diagonals of the S-W matrix, the contents of the copy of the S2 sequence being shifted between shiftings of the copy of the S2 sequence into the columns of the 2-D matrix, wherein, upon completion of the initializing, the 2-D matrix stores m+n+1 anti-diagonals of the S-W matrix, wherein m and n are a number of characters in the S1 and S2 sequences, respectively, and the anti-diagonals are arranged in the 2-D matrix in an order that the anti-diagonals are arranged in the S-W matrix, from the upper left of the S-W matrix to the lower right of the 2-D matrix;
• computing, in parallel, deletion values (D values), insertion values (I values), and match values (C values) for the 2-D matrix;
• conducting a traceback of the 2-D matrix starting from a highest computed C value, to produce a first alignment between characters in the sequences S1 and S2;
• masking out one or more characters in the sequences S1 and S2 based on the first alignment;
• repeating the computing and the conducting a traceback at least one time, to produce at least one additional alignment between the sequences S1 and S2, the first alignment and the at least one additional alignment being non-overlapping, non-intersecting alignments;
• and
• masking out the one or more characters of the sequences S1 and S2 included in additional alignments to one or more excluded characters prior to repeating the computing and the conducting a traceback.