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:
- What conditions to exit recursion
- 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.
# 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: 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: self.multi_backtracking(self.array_E, i, j, new_instance_name) if pass_judgement: 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!