Recently I was learning the sequence alignment algorithm. After I got the alignment matrix, I could find an optimal path, but I was in trouble when I was looking for multiple optimal paths (backtracking)!

My idea is to store the results of multiple paths with multiple instances, and finally loop through all instances of the base class to get the answer. I know the following conditions:

  1. What conditions to exit recursion
  2. When do I need to create a new instance and when I don't create it?

But the problem is in the second condition. I don't know how many optimal results there are, and I don't know how many new instances will be created.

So I want to be able to dynamically generate an instance name with a variable.

like this:

# those equivalent to new_instance_name = ResultSeq()
a="new_instance_name"
create_new_instance(a,ResultSeq)

My result base class is ResultSeq:

class KeepRefs(object):
    """
    reference:https://stackoverflow.com/questions/328851/printing-all-instances-of-a-class#comment167339_328851
    """
    __refs__ = defaultdict(list)

    def __init__(self):
        self.__refs__[self.__class__].append(weakref.ref(self))

    @classmethod
    def get_instances(cls):
        for inst_ref in cls.__refs__[cls]:
            inst = inst_ref()
            if inst is not None:
                yield inst


class ResultSeq(KeepRefs):
    """
    save two
    """
    def __init__(self, seq1="", seq2=""):
        super(ResultSeq, self).__init__()
        self.seq1 = seq1
        self.seq2 = seq2

Below is my recursive code:

def multi_backtracking(self, array, i, j, result_seq):
    """
    :param array: V, E, F
    :param i: row
    :param j: col
    :param result_seq: new instance of the class ResultSeq
    :return: Multiple alignment results
    """

    def create_new_obj(name, obj):
        """
        I don't know how to do this.
        """
        pass

    if i == 0 and j == 0:
        pass
    else:
        if array is self.array_V:
            if sum(pass_judgement) == 1:
                """
                An optimal path without creating a new instance.
                """
                self.multi_backtracking(self.array_V, i, j, result_seq)
            else:
                """
                Multiple paths, need to create a new instance
                """
                new_instance_name = "xxx"
                create_new_obj(new_instance_name, ResultSeq)
                ...
                if pass_judgement[0]:
                    result_seq.seq1 = self.origin_seq.seq1[i - 1] + result_seq.seq1
                    result_seq.seq2 = self.origin_seq.seq2[j - 1] + result_seq.seq2
                    self.multi_backtracking(self.array_V, i - 1, j - 1, new_instance_name)
                if pass_judgement[1]:
                    self.multi_backtracking(self.array_E, i, j, new_instance_name)
                if pass_judgement[2]:
                    self.multi_backtracking(self.array_F, i, j, new_instance_name)

This is just one of my solutions. If there are better suggestions, I will be happy to accept them, thank you!

0 Answers