Aligns two PDB files, returning a mapping from the chains in pdb1 to the chains of pdb2.
       If allow_multiple_matches is False, we return the best match for each chain in pdb1 if a match exists. The return
        value is a dict mapping
            chain_id_in_pdb1 -> None or a list with a single tuple (chain_id_in_pdb_2, percentage_identity_score)
       where percentage_identity_score is a float. e.g. 'A' -> [('B', 100)]. We return a list to keep the return type
       consistent with the allow_multiple_matches case. Use the match_best_pdb_chains wrapper is you only want one match.

       If allow_multiple_matches is True, we return multiple matches for each chain in pdb1 if any matches exists. The return
        value is a dict mapping
            chain_id_in_pdb1 -> None or a list of tuples of the form (chain_id_in_pdb_2, percentage_identity_score)
       where percentage_identity_score is a float. multiple_match_error_margin is the amount of percentage identity difference
       from the best match that we allow for e.g. a chain may map to chain_id1_in_pdb2 with 78% identity and chain_id2_in_pdb2
       with 76% identity. If chain_id1_in_pdb2 is the best match and multiple_match_error_margin >= 2, chain_id2_in_pdb2 will
       also be returned.

       Parameters: pdb1 and pdb2 are PDB objects from klab.bio.pdb. pdb1_name and pdb2_name are strings describing the
        structures e.g. 'Model' and 'Scaffold'. cut_off is used in the matching to discard low-matching chains.

       If use_seqres_sequences_if_possible is set, we will use the SEQRES sequences for the mapping when those sequences
       exist. At present, it is possible to match a SEQRES sequence in pdb1 against an ATOM sequence in pdb2 if pdb1 has
       a SEQRES sequence for that chain in question and pdb2 does not. We may want to change this behavior in the future
       i.e. only match SEQRES to SEQRES and ATOM to ATOM.
       If use_seqres_sequences_if_possible and a SEQRES sequence does not exist for a chain, we fall back to the ATOM
       sequence.

def match_pdb_chains(pdb1, pdb1_name, pdb2, pdb2_name, cut_off = 60.0, allow_multiple_matches = False, multiple_match_error_margin = 3.0, use_seqres_sequences_if_possible = True):
    '''Aligns two PDB files, returning a mapping from the chains in pdb1 to the chains of pdb2.
       If allow_multiple_matches is False, we return the best match for each chain in pdb1 if a match exists. The return
        value is a dict mapping
            chain_id_in_pdb1 -> None or a list with a single tuple (chain_id_in_pdb_2, percentage_identity_score)
       where percentage_identity_score is a float. e.g. 'A' -> [('B', 100)]. We return a list to keep the return type
       consistent with the allow_multiple_matches case. Use the match_best_pdb_chains wrapper is you only want one match.

       If allow_multiple_matches is True, we return multiple matches for each chain in pdb1 if any matches exists. The return
        value is a dict mapping
            chain_id_in_pdb1 -> None or a list of tuples of the form (chain_id_in_pdb_2, percentage_identity_score)
       where percentage_identity_score is a float. multiple_match_error_margin is the amount of percentage identity difference
       from the best match that we allow for e.g. a chain may map to chain_id1_in_pdb2 with 78% identity and chain_id2_in_pdb2
       with 76% identity. If chain_id1_in_pdb2 is the best match and multiple_match_error_margin >= 2, chain_id2_in_pdb2 will
       also be returned.

       Parameters: pdb1 and pdb2 are PDB objects from klab.bio.pdb. pdb1_name and pdb2_name are strings describing the
        structures e.g. 'Model' and 'Scaffold'. cut_off is used in the matching to discard low-matching chains.

       If use_seqres_sequences_if_possible is set, we will use the SEQRES sequences for the mapping when those sequences
       exist. At present, it is possible to match a SEQRES sequence in pdb1 against an ATOM sequence in pdb2 if pdb1 has
       a SEQRES sequence for that chain in question and pdb2 does not. We may want to change this behavior in the future
       i.e. only match SEQRES to SEQRES and ATOM to ATOM.
       If use_seqres_sequences_if_possible and a SEQRES sequence does not exist for a chain, we fall back to the ATOM
       sequence.
       '''

    try:
        pdb1_chains = [c for c in pdb1.atom_chain_order]
        pdb2_chains = [c for c in pdb2.atom_chain_order]
        unrecognized_residues = set(['X'])

        # Extend the list of chains by the SEQRES chain IDs. These will typically be the same list but, just in case, we take
        # the set union.
        if use_seqres_sequences_if_possible:
            pdb1_chains.extend(pdb1.seqres_chain_order)
            pdb1_chains = sorted(set(pdb1_chains))
            pdb2_chains.extend(pdb2.seqres_chain_order)
            pdb2_chains = sorted(set(pdb2_chains))

        sa = SequenceAligner()

        # This is a hack to ensure that the assertions below hold. The alternative is to fix the logic below (maybe allow the separator character to be a parameter).
        pdb1_name = pdb1_name.replace('_', chr(254))
        pdb2_name = pdb2_name.replace('_', chr(254))

        assert(pdb1_name.find('_') == -1)
        assert(pdb2_name.find('_') == -1)

        kept_chains = []
        for c in pdb1_chains:
            # We do not handle chains with all HETATMs (and not ATOMs) well, generally. These conditions allow for those chains
            seq1 = pdb1.get_chain_sequence_string(c, use_seqres_sequences_if_possible, raise_Exception_if_not_found = False)

            if seq1 and str(seq1) and set(str(seq1)) != unrecognized_residues:
                sa.add_sequence('%s_%s' % (pdb1_name, c), str(seq1))
                kept_chains.append(c)
        pdb1_chains = kept_chains

        kept_chains = []
        for c in pdb2_chains:
            # We do not handle chains with all HETATMs (and not ATOMs) well, generally. These conditions allow for those chains
            seq2 = pdb2.get_chain_sequence_string(c, use_seqres_sequences_if_possible, raise_Exception_if_not_found = False)

            if seq2 and str(seq2) and set(str(seq2)) != unrecognized_residues:
                sa.add_sequence('%s_%s' % (pdb2_name, c), str(seq2))
                kept_chains.append(c)
        pdb2_chains = kept_chains

        if not(pdb1_chains):
            raise ChainMatchingException('No valid sequences were found in %s. Alignment failed.' % pdb1_name)
        elif not(pdb2_chains):
            raise ChainMatchingException('No valid sequences were found in %s. Alignment failed.' % pdb2_name)
        else:
            sa.align()

        chain_matches = dict.fromkeys(pdb1_chains, None)
        for c in pdb1_chains:
            best_matches_by_id = sa.get_best_matches_by_id('%s_%s' % (pdb1_name, c), cut_off = cut_off)
            if best_matches_by_id:
                t = []
                for k, v in best_matches_by_id.iteritems():
                    if k.startswith(pdb2_name + '_'):
                        t.append((v, k))
                if t:
                    # We may have multiple best matches here. Instead of just returning one
                    if allow_multiple_matches:
                        best_matches = sorted(t)
                        best_match_identity = best_matches[0][0]
                        allowed_cutoff = max(cut_off, best_match_identity - multiple_match_error_margin)
                        chain_matches[c] = []
                        for best_match in best_matches:
                            if best_match[0] >= allowed_cutoff:
                                chain_matches[c].append((best_match[1].split('_')[1], best_match[0]))
                        assert(len(chain_matches[c]) > 0)
                    else:
                        best_match = sorted(t)[0]
                        chain_matches[c] = [(best_match[1].split('_')[1], best_match[0])]

        return chain_matches
    except ChainMatchingException, e:
        raise
    except Exception, e:
        raise ChainMatchingException()