Partial match expansion, optimized for long sub-sequences.
502434
def _py_expand_long(subsequence, sequence, max_l_dist):
    """"""
    # The additional optimization in this version is to limit the part of
    # the sub-sequence inspected for each sequence character.  The start and
    # end of the iteration are limited to the range where the scores are
    # smaller than the maximum allowed distance.  Additionally, once a good
    # expansion has been found, the range is further reduced to where the
    # scores are smaller than the score of the best expansion found so far.

    subseq_len = len(subsequence)
    if subseq_len == 0:
        return (0, 0)

    # Initialize the scores array with values for just skipping sub-sequence
    # chars.
    scores = list(range(1, subseq_len + 1))

    min_score = subseq_len
    min_score_idx = -1
    max_good_score = max_l_dist
    new_needle_idx_range_start = 0
    new_needle_idx_range_end = subseq_len - 1

    for seq_index, char in enumerate(sequence):
        # calculate scores, one for each character in the sub-sequence
        needle_idx_range_start = new_needle_idx_range_start
        needle_idx_range_end = min(subseq_len, new_needle_idx_range_end + 1)

        a = seq_index
        c = a + 1

        if c <= max_good_score:
            new_needle_idx_range_start = 0
            new_needle_idx_range_end = 0
        else:
            new_needle_idx_range_start = None
            new_needle_idx_range_end = -1

        for subseq_index in range(needle_idx_range_start, needle_idx_range_end):
            b = scores[subseq_index]
            c = scores[subseq_index] = min(
                a + (char != subsequence[subseq_index]),
                b + 1,
                c + 1,
            )
            a = b

            if c <= max_good_score:
                if new_needle_idx_range_start is None:
                    new_needle_idx_range_start = subseq_index
                new_needle_idx_range_end = max(
                    new_needle_idx_range_end,
                    subseq_index + 1 + (max_good_score - c),
                )

        # bail early when it is impossible to find a better expansion
        if new_needle_idx_range_start is None:
            break

        # keep the minimum score found for matches of the entire sub-sequence
        if needle_idx_range_end == subseq_len and c <= min_score:
            min_score = c
            min_score_idx = seq_index
            if min_score < max_good_score:
                max_good_score = min_score

    return (min_score, min_score_idx + 1) if min_score <= max_l_dist else (None, None)
1281808
def find_matches(text):
    
    """
    path = os.path.expanduser(text)
    if os.path.isdir(path) and not path.endswith('/'):
        return [ text + '/' ]

    pattern = path + '*'
    is_implicit_cwd = not (path.startswith('/') or path.startswith('./'))
    if is_implicit_cwd:
        pattern = './' + pattern
    rawlist = glob.glob(pattern)
    ret = []
    for fname in rawlist:
        if is_implicit_cwd:
            fname = fname[2:]
        if os.path.isdir(fname):
            ret.append(fname + '/')
        else:
            ret.append(fname)
    return ret
1081432
function cloneMatches(words) {
  var result = {}
  var key
  var match

  for (key in words) {
    match = words[key]

    result[key] = {
      matches: match.matches,
      stem: match.stem,
      score: match.score
    }
  }

  return result
}
240950
private char matchPrefix(String str1, String str2) {
        //here always str1.startsWith(str2) colorless!color
        char rel = IMappingElement.IDK;
        int spacePos1 = str1.indexOf(' ');
        String suffix = str1.substring(str2.length());
        if (-1 < spacePos1 && !suffixes.containsKey(suffix)) {//check suffixes - pole vault=pole vaulter
            if (str2.length() == spacePos1) {//plant part<plant
                rel = IMappingElement.LESS_GENERAL;
            } else {//plant part<plan
                String left = str1.substring(0, spacePos1);
                char secondRel = match(left, str2);
                if (IMappingElement.MORE_GENERAL == secondRel ||
                        IMappingElement.EQUIVALENCE == secondRel) {
                    rel = IMappingElement.LESS_GENERAL;
                } else { //?,<,!
                    rel = secondRel;
                }
            }
        } else {
            //spelling: -tree and tree
            if (suffix.startsWith("-")) {
                suffix = suffix.substring(1);
            }
            if (suffix.endsWith("-") || suffix.endsWith(";") || suffix.endsWith(".") || suffix.endsWith(",") || suffix.endsWith("-")) {
                suffix = suffix.substring(0, suffix.length() - 1);
            }
            if (suffixes.containsKey(suffix)) {
                rel = suffixes.get(suffix);
                rel = reverseRelation(rel);
            }

            //another approximation = Gversion4
//            if (rel == MatchManager.LESS_GENERAL || rel == MatchManager.MORE_GENERAL) {
//                rel = MatchManager.EQUIVALENCE;
//            }
        }

        //filter = Gversion3
//        if (MatchManager.LESS_GENERAL == rel || MatchManager.MORE_GENERAL == rel) {
//            rel = MatchManager.EQUIVALENCE;
//        }

        return rel;
    }
410214
@Override
    public int matches(Replaceable text,
                       int[] offset,
                       int limit,
                       boolean incremental) {
        int c;
        if (offset[0] < limit &&
            contains(c = text.char32At(offset[0]))) {
            offset[0] += UTF16.getCharCount(c);
            return U_MATCH;
        }
        if (offset[0] > limit && contains(text.char32At(offset[0]))) {
            // Backup offset by 1, unless the preceding character is a
            // surrogate pair -- then backup by 2 (keep offset pointing at
            // the lead surrogate).
            --offset[0];
            if (offset[0] >= 0) {
                offset[0] -= UTF16.getCharCount(text.char32At(offset[0])) - 1;
            }
            return U_MATCH;
        }
        if (incremental && offset[0] == limit) {
            return U_PARTIAL_MATCH;
        }
        return U_MISMATCH;
    }
631425
def partial(cls, prefix, source):
        """"""
        match = prefix + "."
        
        matches = cls([(key[len(match):], source[key]) for key in source if key.startswith(match)])
        
        if not matches:
            raise ValueError()
        
        return matches
1318662
def match_subfeats(f1, f2, dbx1, dbx2, featuretype=None, slop=False):
    
    f1c, f2c = list(dbx1.children(f1, featuretype=featuretype, order_by='start')), \
            list(dbx2.children(f2, featuretype=featuretype, order_by='start'))

    lf1c, lf2c = len(f1c), len(f2c)
    if match_nchildren(f1c, f2c):
        if lf1c > 0 and lf2c > 0:
            exclN = set()
            if featuretype.endswith('UTR') or featuretype == 'exon':
                N = []
                if featuretype.startswith('five_prime'):
                    N = [1] if f1.strand == "+" else [lf1c]
                elif featuretype.startswith('three_prime'):
                    N = [lf1c] if f1.strand == "+" else [1]
                else:   # infer UTR from exon collection
                    N = [1] if 1 == lf1c else [1, lf1c]

                for n in N:
                    if match_Nth_child(f1c, f2c, N=n, slop=slop):
                        exclN.add(n-1)
                    else:
                        return False

            for i, (cf1, cf2) in enumerate(zip(f1c, f2c)):
                if i in exclN: continue
                if not match_span(cf1, cf2):
                    return False
    else:
        if (lf1c, lf2c) in [(0, 1), (1, 0)] and slop \
                and featuretype.endswith('UTR'):
            return True

        return False

    return True
955793
def locate(self, pattern):
        '''

        '''
        if len(pattern) > len(self):
            raise ValueError('Search pattern longer than searchable ' +
                             'sequence.')
        seq = self.seq

        pattern = str(pattern).upper()
        re_pattern = '(?=' + pattern + ')'
        matches = [index.start() % len(self) for index in
                   re.finditer(re_pattern, seq)]

        return matches
1118802
def ComputeFortranSuffixes(suffixes, ppsuffixes):
    """"""
    assert len(suffixes) > 0
    s = suffixes[0]
    sup = s.upper()
    upper_suffixes = [_.upper() for _ in suffixes]
    if SCons.Util.case_sensitive_suffixes(s, sup):
        ppsuffixes.extend(upper_suffixes)
    else:
        suffixes.extend(upper_suffixes)
512801
def concat_align(fastas):
    
    # read in sequences
    fa2len = {}
    seqs = {}
    IDs = []
    for fasta in fastas:
        seqs[fasta] = {}
        for seq in parse_fasta(fasta):
            ID = seq[0].split('>')[1].split()[0]
            IDs.append(ID)
            seqs[fasta][ID] = seq[1]
        fa2len[fasta] = len(seq[1])
    # concat sequences
    IDs = set(IDs)
    concat = {}
    for fasta in fastas:
        for ID in IDs:
            if ID not in concat:
                concat[ID] = []
            if ID not in seqs[fasta]:
                concat[ID].append('-'*fa2len[fasta])
            else:
                concat[ID].append(seqs[fasta][ID])
    return concat
835536
def alignment_to_partials(alignment, missing_data=None):
    
    partials_dict = {}
    for (name, sequence) in alignment.get_sequences():
        datatype = 'dna' if alignment.is_dna() else 'protein'
        partials_dict[name] = seq_to_partials(sequence, datatype)

    if missing_data is not None:
        l = len(alignment)
        for name in missing_data:
            if name not in partials_dict:
                partials_dict[name] = seq_to_partials('-'*l, datatype)
    return partials_dict
708097
def match_entries(entries, pattern):
    """"""
    matching = []

    for variant in expand_braces(pattern):
        matching.extend(fnmatch.filter(entries, variant))

    return list(_deduplicate(matching))
1333888
def _recursive_matches(self, nodes, count):
        """"""
        assert self.content is not None
        if count >= self.min:
            yield 0, {}
        if count < self.max:
            for alt in self.content:
                for c0, r0 in generate_matches(alt, nodes):
                    for c1, r1 in self._recursive_matches(nodes[c0:], count+1):
                        r = {}
                        r.update(r0)
                        r.update(r1)
                        yield c0 + c1, r
565088
def match_indices(match):
    """"""
    a, b, size = match
    for i in range(size):
        yield a + i, b + i
1253225
def pattern_match(data, values, level=None, regexp=False, has_nan=True):
    
    matches = np.array([False] * len(data))
    if not isinstance(values, collections.Iterable) or isstr(values):
        values = [values]

    # issue (#40) with string-to-nan comparison, replace nan by empty string
    _data = data.copy()
    if has_nan:
        _data.loc[[np.isnan(i) if not isstr(i) else False for i in _data]] = ''

    for s in values:
        if isstr(s):
            pattern = re.compile(_escape_regexp(s) + '$' if not regexp else s)
            subset = filter(pattern.match, _data)
            depth = True if level is None else find_depth(_data, s, level)
            matches |= (_data.isin(subset) & depth)
        else:
            matches |= data == s
    return matches
1171181
def _normalize_seqs(s, t):
    """"""
    for ids in s:
        obj = s[ids]
        [obj.norm_freq.update({sample: 1.0 * obj.freq[sample] / (t[sample]+1) * 1000000}) for sample in obj.norm_freq]
        s[ids] = obj
    return s
384834
def dna_to_re(seq):
    

    seq = seq.replace('K', '[GT]')
    seq = seq.replace('M', '[AC]')
    seq = seq.replace('R', '[AG]')
    seq = seq.replace('Y', '[CT]')
    seq = seq.replace('S', '[CG]')
    seq = seq.replace('W', '[AT]')
    seq = seq.replace('B', '[CGT]')
    seq = seq.replace('V', '[ACG]')
    seq = seq.replace('H', '[ACT]')
    seq = seq.replace('D', '[AGT]')
    seq = seq.replace('X', '[GATC]')
    seq = seq.replace('N', '[GATC]')

    return re.compile(seq)