parameters: (graph, start_seg, end_seg, target_length, sequence, scoring_scheme,
                             expected_scaled_score)
return_statement: return paths_and_scores, progressive_path_search
docstring: Given a sequence and target length, this function finds the best paths from the start
      segment to the end segment.
docstring_summary: Given a sequence and target length, this function finds the best paths from the start
      segment to the end segment.
docstring_tokens: Given a sequence and target length this function finds the best paths from the start segment to the end segment .
function: def get_best_paths_for_seq(graph, start_seg, end_seg, target_length, sequence, scoring_scheme,
                             expected_scaled_score):
      """
      Given a sequence and target length, this function finds the best paths from the start
      segment to the end segment.
      """
      assert graph.overlap == 0
  
      # Limit the path search to lengths near the target.
      min_length = min(int(round(target_length * settings.MIN_RELATIVE_PATH_LENGTH)),
                       target_length - settings.RELATIVE_PATH_LENGTH_BUFFER_SIZE)
      max_length = max(int(round(target_length * settings.MAX_RELATIVE_PATH_LENGTH)),
                       target_length + settings.RELATIVE_PATH_LENGTH_BUFFER_SIZE)
  
      # If there are few enough possible paths, we just try aligning to them all.
      try:
          paths = all_paths(graph, start_seg, end_seg, min_length, max_length)
          progressive_path_search = False
  
      # If there are too many paths to try exhaustively, we use a progressive approach to find
      # the best path.
      except TooManyPaths:
          progressive_path_search = True
          paths = progressive_path_find(graph, start_seg, end_seg, min_length, max_length,
                                        sequence, scoring_scheme, expected_scaled_score)
  
      # Sort by length discrepancy from the target so the closest length matches come first.
      paths = sorted(paths, key=lambda x: abs(target_length - graph.get_bridge_path_length(x)))
  
      # We now align the consensus to each of the possible paths.
      paths_and_scores = []
      for path in paths:
          path_len = graph.get_bridge_path_length(path)
          length_discrepancy = abs(path_len - target_length)
  
          # If there is a consensus sequence, then we actually do an alignment against the path.
          if sequence:
              path_seq = graph.get_path_sequence(path)
              alignment_result = fully_global_alignment(sequence, path_seq, scoring_scheme,
                                                        True, 1000)
              if not alignment_result:
                  continue
  
              seqan_parts = alignment_result.split(',', 9)
              raw_score = int(seqan_parts[6])
              scaled_score = float(seqan_parts[7])
  
          # If there isn't a consensus sequence (i.e. the start and end overlap), then each
          # path is only scored on how well its length agrees with the target length.
          else:
              raw_score = get_num_agreement(path_len, target_length) * 100.0
              scaled_score = 100.0
  
          paths_and_scores.append((path, raw_score, length_discrepancy, scaled_score))
  
      # Sort the paths from highest to lowest quality.
      paths_and_scores = sorted(paths_and_scores, key=lambda x: (-x[1], x[2], -x[3]))
  
      # Don't bother keeping paths which are much worse than the best.
      if paths_and_scores:
          best_scaled_score = paths_and_scores[0][3]
          min_scaled_score = best_scaled_score * 0.95
          paths_and_scores = [x for x in paths_and_scores if x[3] >= min_scaled_score]
  
      return paths_and_scores, progressive_path_search
function_tokens: def get_best_paths_for_seq ( graph , start_seg , end_seg , target_length , sequence , scoring_scheme , expected_scaled_score ) : assert graph . overlap == 0 # Limit the path search to lengths near the target. min_length = min ( int ( round ( target_length * settings . MIN_RELATIVE_PATH_LENGTH ) ) , target_length - settings . RELATIVE_PATH_LENGTH_BUFFER_SIZE ) max_length = max ( int ( round ( target_length * settings . MAX_RELATIVE_PATH_LENGTH ) ) , target_length + settings . RELATIVE_PATH_LENGTH_BUFFER_SIZE ) # If there are few enough possible paths, we just try aligning to them all. try : paths = all_paths ( graph , start_seg , end_seg , min_length , max_length ) progressive_path_search = False # If there are too many paths to try exhaustively, we use a progressive approach to find # the best path. except TooManyPaths : progressive_path_search = True paths = progressive_path_find ( graph , start_seg , end_seg , min_length , max_length , sequence , scoring_scheme , expected_scaled_score ) # Sort by length discrepancy from the target so the closest length matches come first. paths = sorted ( paths , key = lambda x : abs ( target_length - graph . get_bridge_path_length ( x ) ) ) # We now align the consensus to each of the possible paths. paths_and_scores = [ ] for path in paths : path_len = graph . get_bridge_path_length ( path ) length_discrepancy = abs ( path_len - target_length ) # If there is a consensus sequence, then we actually do an alignment against the path. if sequence : path_seq = graph . get_path_sequence ( path ) alignment_result = fully_global_alignment ( sequence , path_seq , scoring_scheme , True , 1000 ) if not alignment_result : continue seqan_parts = alignment_result . split ( ',' , 9 ) raw_score = int ( seqan_parts [ 6 ] ) scaled_score = float ( seqan_parts [ 7 ] ) # If there isn't a consensus sequence (i.e. the start and end overlap), then each # path is only scored on how well its length agrees with the target length. else : raw_score = get_num_agreement ( path_len , target_length ) * 100.0 scaled_score = 100.0 paths_and_scores . append ( ( path , raw_score , length_discrepancy , scaled_score ) ) # Sort the paths from highest to lowest quality. paths_and_scores = sorted ( paths_and_scores , key = lambda x : ( - x [ 1 ] , x [ 2 ] , - x [ 3 ] ) ) # Don't bother keeping paths which are much worse than the best. if paths_and_scores : best_scaled_score = paths_and_scores [ 0 ] [ 3 ] min_scaled_score = best_scaled_score * 0.95 paths_and_scores = [ x for x in paths_and_scores if x [ 3 ] >= min_scaled_score ] return paths_and_scores , progressive_path_search