Technically, your search strings are not regular expressions, nor is it sensible to approach this as a regex problem.

This looks like a Protein sequence alignment problem. Use the tools of the trade. Or do you plan to research new algorithms?