parameters: (graph, start, end, min_length, max_length, sequence, scoring_scheme,
                            expected_scaled_score)
return_statement: return [x for x in final_paths if min_length <= graph.get_path_length(x) <= max_length]
docstring: This function is called when all_paths fails due to too many paths. It searches for paths by
      extended outward from both the start and end, making paths where the two searches meet. When
      the number of working paths gets too high, it is culled by performing alignments with the
      in-progress paths.
docstring_summary: This function is called when all_paths fails due to too many paths. It searches for paths by
      extended outward from both the start and end, making paths where the two searches meet. When
      the number of working paths gets too high, it is culled by performing alignments with the
      in-progress paths.
docstring_tokens: This function is called when all_paths fails due to too many paths . It searches for paths by extended outward from both the start and end making paths where the two searches meet . When the number of working paths gets too high it is culled by performing alignments with the in - progress paths .
function: def progressive_path_find(graph, start, end, min_length, max_length, sequence, scoring_scheme,
                            expected_scaled_score):
      """
      This function is called when all_paths fails due to too many paths. It searches for paths by
      extended outward from both the start and end, making paths where the two searches meet. When
      the number of working paths gets too high, it is culled by performing alignments with the
      in-progress paths.
      """
      reverse_sequence = reverse_complement(sequence)
  
      # This set will collect all of the final paths produced. Paths are stored here as tuples
      # (because they are hashable for a set).
      final_paths = set()
  
      # We will work with a list of forward paths and a list of reverse paths. We set them up now
      # along with dictionaries to allow easy access to all working paths which end in a particular
      # segment.
      forward_working_paths = [[start]]
      reverse_working_paths = [[-end]]
  
      # Knowing the start/end depth lets us put some limits on how many times a segment can be in a
      # path, which we use to avoid going through loops forever.
      start_seg = graph.segments[abs(start)]
      end_seg = graph.segments[abs(end)]
      start_end_depth = weighted_average(start_seg.depth, end_seg.depth,
                                         start_seg.get_length(), end_seg.get_length())
  
      # If one of the two directions gets clogged, then only the other direction will be advanced.
      # If both directions get clogged, then the culling score fraction will be increased (brought
      # closer to 1.0) such that path culling is more aggressive.
      forward_clogged = False
      reverse_clogged = False
  
      while True:
          if not forward_clogged:
              shortest_reverse_path = min(graph.get_path_length(x[1:]) for x in reverse_working_paths)
              reverse_paths_dict = build_path_dictionary(reverse_working_paths)
              forward_working_paths = advance_paths(forward_working_paths, reverse_paths_dict,
                                                    shortest_reverse_path, final_paths, False,
                                                    sequence, scoring_scheme, expected_scaled_score,
                                                    graph, start_end_depth, max_length,
                                                    settings.PROGRESSIVE_PATH_SEARCH_SCORE_FRACTION)
              if not forward_working_paths:
                  break
              elif len(forward_working_paths) > settings.PROGRESSIVE_PATH_SEARCH_MAX_WORKING_PATHS:
                  forward_clogged = True
  
          if not reverse_clogged:
              shortest_forward_path = min(graph.get_path_length(x[1:]) for x in forward_working_paths)
              forward_paths_dict = build_path_dictionary(forward_working_paths)
              reverse_working_paths = advance_paths(reverse_working_paths, forward_paths_dict,
                                                    shortest_forward_path, final_paths, True,
                                                    reverse_sequence, scoring_scheme,
                                                    expected_scaled_score, graph, start_end_depth,
                                                    max_length,
                                                    settings.PROGRESSIVE_PATH_SEARCH_SCORE_FRACTION)
              if not reverse_working_paths:
                  break
              elif len(reverse_working_paths) > settings.PROGRESSIVE_PATH_SEARCH_MAX_WORKING_PATHS:
                  reverse_clogged = True
  
          # If both paths have clogged up, then we give up!
          if forward_clogged and reverse_clogged:
              return []
  
      # Trim the start/end segments, filter for appropriate length and return the final paths!
      final_paths = [list(x)[1:-1] for x in final_paths]
      return [x for x in final_paths if min_length <= graph.get_path_length(x) <= max_length]
function_tokens: def progressive_path_find ( graph , start , end , min_length , max_length , sequence , scoring_scheme , expected_scaled_score ) : reverse_sequence = reverse_complement ( sequence ) # This set will collect all of the final paths produced. Paths are stored here as tuples # (because they are hashable for a set). final_paths = set ( ) # We will work with a list of forward paths and a list of reverse paths. We set them up now # along with dictionaries to allow easy access to all working paths which end in a particular # segment. forward_working_paths = [ [ start ] ] reverse_working_paths = [ [ - end ] ] # Knowing the start/end depth lets us put some limits on how many times a segment can be in a # path, which we use to avoid going through loops forever. start_seg = graph . segments [ abs ( start ) ] end_seg = graph . segments [ abs ( end ) ] start_end_depth = weighted_average ( start_seg . depth , end_seg . depth , start_seg . get_length ( ) , end_seg . get_length ( ) ) # If one of the two directions gets clogged, then only the other direction will be advanced. # If both directions get clogged, then the culling score fraction will be increased (brought # closer to 1.0) such that path culling is more aggressive. forward_clogged = False reverse_clogged = False while True : if not forward_clogged : shortest_reverse_path = min ( graph . get_path_length ( x [ 1 : ] ) for x in reverse_working_paths ) reverse_paths_dict = build_path_dictionary ( reverse_working_paths ) forward_working_paths = advance_paths ( forward_working_paths , reverse_paths_dict , shortest_reverse_path , final_paths , False , sequence , scoring_scheme , expected_scaled_score , graph , start_end_depth , max_length , settings . PROGRESSIVE_PATH_SEARCH_SCORE_FRACTION ) if not forward_working_paths : break elif len ( forward_working_paths ) > settings . PROGRESSIVE_PATH_SEARCH_MAX_WORKING_PATHS : forward_clogged = True if not reverse_clogged : shortest_forward_path = min ( graph . get_path_length ( x [ 1 : ] ) for x in forward_working_paths ) forward_paths_dict = build_path_dictionary ( forward_working_paths ) reverse_working_paths = advance_paths ( reverse_working_paths , forward_paths_dict , shortest_forward_path , final_paths , True , reverse_sequence , scoring_scheme , expected_scaled_score , graph , start_end_depth , max_length , settings . PROGRESSIVE_PATH_SEARCH_SCORE_FRACTION ) if not reverse_working_paths : break elif len ( reverse_working_paths ) > settings . PROGRESSIVE_PATH_SEARCH_MAX_WORKING_PATHS : reverse_clogged = True # If both paths have clogged up, then we give up! if forward_clogged and reverse_clogged : return [ ] # Trim the start/end segments, filter for appropriate length and return the final paths! final_paths = [ list ( x ) [ 1 : - 1 ] for x in final_paths ] return [ x for x in final_paths if min_length <= graph . get_path_length ( x ) <= max_length ]