pyampact.alignmentUtils.dp

pyampact.alignmentUtils.dp(local_costs, penalty=0.1, gutter=0.0, G=0.5)[source]

Use dynamic programming to find a min-cost path through a matrix of local costs.

Parameters:

  • local_costs (np.ndarray) – A 2D matrix of local costs, where each cell represents the cost associated with that specific position.

  • penalty (float, optional) – An additional cost incurred for moving in the horizontal or vertical direction (i.e., (0,1) and (1,0) steps). Default is 0.1.

  • gutter (float, optional) – A proportion of edge length that allows for deviations away from the bottom-left corner (-1,-1) in the optimal path. Default is 0.0, meaning the path must reach the top-right corner.

  • G (float, optional) – A proportion of the edge length considered for identifying gulleys in the cost matrix. Default is 0.5.

Returns:

  • p (np.ndarray) – An array of row indices corresponding to the best path.

  • q (np.ndarray) – An array of column indices corresponding to the best path.

  • total_costs (np.ndarray) – A 2D array of minimum costs to reach each cell in the local costs matrix.

  • phi (np.ndarray) – A traceback matrix indicating the preceding best-path step for each cell, where: - 0 indicates a diagonal predecessor. - 1 indicates the previous column (same row). - 2 indicates the previous row (same column).