Losing Alignments Due to Asymmetric Substitution Matrix

[esaliya]

There are a couple of things that we may need to think in the future due to the S matrix being asymmetric. This is the first issue to think about.

We lose pairs in the resultant matrix because we only compute the top half due to this asymmetry in the resultant ASAt.

• Each process in the process grid computes their upper halves only. For example P_ij and P_ji collectively computes all non-zero overlaps of process grid cell ij (or ji).

• When the matrix is symmetric this works flawlessly because the top half of P_ij captures all the non-zero overlaps of the bottom half of P_ji, which is not computed by P_ji. In the same way, the top half of P_ji captures all the non-zero elements of the bottom half of P_ij.

• However, when the matrix is asymmetric the above condition does not hold true anymore. To fix it we can do the following.

  • Each process, P_ij, can send the non-zero pair IDs of their bottom halves to P_ji using MPI_Isend asynchornously.

  • While they receive these bottom half pair IDs from their partner processes, they can compute alignments for the non-zero elements in their top-halves.

  • Once, the alignments are computed and done for the partner pair IDs, each process can check which of the received pair IDs were NOT in their top-halves. Each process should perform alignments for those pair IDs that were not previously computed from this received set.

[aydinbuluc]

@roguzsel is this issue still relevant or resolved?

[roguzsel]

This is resolved. I do C += C^T when the substitute matrix is utilized.