BACKGROUND
the proliferation of known or suspected protein sequences in the post-genomic era and the slower, but steady, progress in protein structure determination implies that there are a large number of proteins with no experimentally determined structure but with varying homology to a protein of known structure.
when such proteins are of experimental or practical interest, several approaches can be used to generate some form of approximate structural information to aid in the design or interpretation of biochemical experiments.
for example, homology modeling can be used to build a model structure for the protein of interest based on the known structure.
first introduced in  <dig>  <cit> , homology modeling has become a more commonly applied tool in recent years.
however, homology modeling remains sensitive not only to the multiple sequence alignment  of homologous proteins, but also to the particular algorithms used in the structural modeling  <cit> .
moreover, the confidence assigned to such models is dependent on the evolutionary relatedness of the modeling target to the known template.
an alternative approach is to map information from the msa onto the known structure, typically via color-coding or similar visual procedures.
such combinations of structural and sequence information do not contain as much information as carefully made homology models, but they permit many of the same applications as homology modeling, such as predicting the location and/or function of potentially interesting residues, and are also useful in evaluating and modifying homology models themselves: a homology model that places a site of frequent gaps and insertions in the middle of a central beta strand rather than on a surface loop is unlikely to be reliable.
scoring the msa onto the known structure is driven only by the msa, without potential bias from the modeling or threading programs.
this approach was formalized in  <dig> with pdbalign  <cit> , a command-line application taking as inputs a protein structure in pdb format and an msa in gcg format.
pdbalign generates a new pdb file retaining the original sequence and spatial information, but with homology information written to the b factor  field of the output pdb file.
scoring schemes cannot be added to pdbalign without changing the source code and recompiling, and the program is similarly limited in its ability to handle residues other than the canonical  <dig> amino acids without manual editing of the pdb file.
in the years since the appearance of pdbalign, a number of other programs have been developed that permit such evaluation of sequence information in various contexts, including swissmodel  <cit> , chimera  <cit> , protein explorer  <cit> , consurf  <cit> , sting  <cit> , and several commercial packages.
most recently, multiseq has been reported  <cit>  as an extension to the popular vmd structural analysis software  <cit>  with an emphasis on evolutionary relationships.
the underlying trend in more recent software is therefore to tie presentation of information from the msa to a single viewing environment, such as chimera or vmd.
such software is thus not well suited to collaborations among workers who prefer different environments and may not be well-suited to automated operation because of the emphasis on integration with a viewing and analysis package or web server largely driven by a graphical user interface .
therefore, we believe there is a niche for a flexible, up-to-date, open-source command-line tool for mapping the homology information from protein sequence alignments onto protein structures.
we have developed homolmapper as a command-line python application for such work.
homolmapper places special emphasis on visualizing additional information such as the location of mutations, on defining and characterizing a subfamily within a given alignment, and on allowing runtime extensibility for user-defined scoring schemes and for handling of noncanonical residues in the structure and/or alignment.
homolmapper currently uses pdb files and several different msa formats as inputs and outputs a new pdb file with homology information written to fields that do not change the spatial information.
this permits the user to view the results in the viewing environment of their own choice.
it is also possible to use a position-specific scoring matrix  generated by psi-blast  <cit>  instead of an msa.
homolmapper is small , portable, and requires only a working python installation of version  <dig>  or later  <cit> .
implementation and
RESULTS
rationale for program operation
within a given pdb file, individual atoms are assigned a single atom or hetatm record identifying the atom and locating it within a 3-dimensional cartesian coordinate system .
within such records, individual fields such as residue number, atom name, and z coordinate are defined by column offset.
the pdb format also provides several additional fields that provide either additional experimental detail about the structure determination  or provide additional descriptive information .
b factor has been previously used as a convenient field for storing information about homology  <cit> .
like b field, occupancy is a 6-column floating-point column well suited to storing such information; the other fields dispensable for unique specification of the atom name and location are smaller  and are less frequently supported by viewing programs.
homolmapper writes information to occupancy and/or b factor; additional outputs are written to the segid field , albeit with less precision.
the element field can also be used.
the primary output is a new pdb file to permit the user to evaluate the results in the viewing program of choice.
of course, this imposes fundamental limitations on the nature of the outputs, because they must fit the pdb standard.
homolmapper results also must be archived as complete structure files rather than simple parameter lists, although the extra storage requirements are modest and such files are by their nature stand-alone and not linked to a single "master" structure file.
homolmapper can also report scores as a tab-delimited text file for analysis with other software tools.
overall architecture
homolmapper is written in python using a functional approach and has an overall layout resembling a c program .
extensive commenting is provided within the main script for users wishing to alter the program itself, but such editing is not needed for normal operations nor for many types of user customization.
homolmapper is a strictly command-line application; user control is provided via a large number of flags that can be added to the command line to control various aspects of program behavior .
homolmapper can also use specialized text files to import information on a number of options, such as subfamilies, mutations, non-standard residues, and additional scoring schemes.
it is possible to supply some or all of the desired settings, including input files, in a text file for repetitive tasks or to supply preferred settings.
this feature also aids in automation of homolmapper for batch jobs.
homolmapper can also generate such settings files, as well as generating files containing the subfamily definition, protein sequences from the input pdb file, or runtime alignment .
homolmapper output files have headers indicating their source; most provide basic information about the run parameters used in preparing the file.
matching the structure to the alignment
to produce meaningful output, software such as homolmapper must synchronize the protein structure and the msa by matching the sequence contained in the protein structure to a sequence in the msa.
in homolmapper, this matching process is by default automatic.
homolmapper will first check for exact matches to the entire structure sequence  and then, assuming no matches were found, for exact matches to each chain in the pdb file .
if no significant matches are found at this point, the sequence in each chain will be broken into short blocks, and exact matches to those blocks will be used to match the sequence .
should this fail, a slower recursive algorithm will be employed .
if no significant matches can be found, an error will be triggered and execution will cease.
the chosen matched sequence is used to determine which portions of the structure are exact matches to the msa; only these residues will be scored, so that the presence of exogenous sequence such as a his tag will not result in spurious results.
by default, homolmapper will pass all unscored atoms to the output file without changes, but it is possible to set the output fields of unscored atoms to zero  or to empty fields  if so requested.
the user has control over several aspects of this process.
it is possible to choose the first matching method used, so that methods can be skipped if so chosen.
it is also possible to redefine the threshold of significance for the entire matched sequence, to specify the size of the peptide blocks used at the third step, and to specify the smallest significant fragments used by the recursive algorithm.
additionally, the user can supply the name of one of the sequences in the msa.
if such a name is supplied and matches a name in the msa, homolmapper will only test that name as a significant match.
if an invalid name is supplied, homolmapper will warn the user and use the default method.
scoring schemes and reference sequences
homolmapper can score sequences by gaps, insertions, identity, shannon's entropy  <cit> , information content, and several similarity schemes.
shannon's entropy and information content can also use user-defined amino acid sets, which readily permits correction for chemical similarity among residues in entropy scoring  <cit> .
these schemes are by default reported in bits , but the user can choose an alternative base for the logarithm.
rather than trying to use a single objective function for scoring the msa including gaps  <cit> , homolmapper uses separate analysis of gaps and insertion.
this reflects its intended uses in analyzing homology models and in structure/function studies, because gaps and insertions are useful in evaluating the overall correctness of fold in homology modeling with distant templates .
the elongation of surface loops has also been implicated in cold adaptation of enzymes from psychrophilic organisms  <cit> .
gaps are here defined as positions where the matched sequence lacks amino acids but other proteins in the alignment have them, and insertions are defined as positions where the matched sequence has amino acids but at least one other protein lacks them.
gaps and insertions are therefore always scored relative to the matched sequence.
gaps and insertions can be scored by length or by frequency .
homolmapper offers several approaches for calculating similarity of amino acids.
identity can be calculated by a simple arithmetic procedure.
this procedure compares each residue in the alignment to the aligned residue in a reference sequence, and the number of identical residues will be divided by the total number of sequences in the alignment.
alternately, the number of identical residues can be divided by the number of sequences that have a residue at the position in question to avoid penalizing for gaps, which can be useful for locating rare but conserved insertions.
several types of similarity can be calculated via a matrix lookup procedure which makes it easy to add scoring schemes by importing them as text files at runtime.
blosum <dig>  <cit> , pam <dig>  <cit> , and charge matrices are incorporated into the homolmapper script itself.
a total of  <dig> other scoring schemes are supplied as formatted text files as part of the homolmapper distribution, including series of blosum  <cit> , pam  <cit> , and gonnet  <cit>  substitution matrices and additional scoring matrices based on physical properties such as hydrophobicity, sidechain entropy of folding, and nonpolar accessible surface area .
any or all of these schemes can be imported at runtime as needed, although homolmapper will use at most two such schemes because of the limited number of output fields available .
homolmapper can report both the score  and the variation  at each position for any matrix scheme, permitting assessment of both conservation and variability .
variation can be reported as standard deviation or standard error of the scores at each position in the msa, or as the range of scores spanned at each position.
homolmapper also reports mean, standard deviation, and score diversity for the scores themselves in the header of the output pdb file.
score diversity is here calculated as the percentage of the maximum shannon entropy for the score in question, and is therefore akin to the dops measure used in assessing alignment scoring in scorecons  <cit> .
scoring schemes can also be reported as z-scores relative to the calculated mean and standard deviation.
three substitution matrices are built-in to the homolmapper application , while the others are supplied as external matrices that can be loaded at runtime if so desired.
some of the external matrices are supplied in a compressed archive , while others are not .
the expanded blosum <dig> and pam <dig> schemes  incorporate standard values for 'b,' 'x,' and 'z' amino acids.
in addition to identity and the matrix-lookup schemes, homolmapper can score using user-defined amino acid sets.
such sets treat a group of amino acids as equivalent for scoring.
homolmapper can report the percentage of sequences having a member of such a set at each position in the structure , or it can define all amino acids as belonging to sets and then report the percentage of sequences having members of the same set as a reference sequence for each position .
this feature gives the user the ability to quickly look for features such as hydrogen bond donors at an unusual ph without taking the time to create a suitable scoring matrix.
it is possible to disable gap penalties for scoring by matrix-lookup and by user-defined amino acid sets.
several of these scoring schemes are relative.
for example, calculating percent identity implies the existence of a reference sequence to which the others will be compared.
by default, homolmapper uses the matched sequence  as the reference sequence; as discussed above, this is always the case for scoring gaps or insertions.
however, schemes such as identity or similarity matrices can instead use a consensus sequence or a different sequence found in the alignment as the reference sequence.
consensus sequences can be supplied as part of the input msa, permitting import of consensus sequences from sources such as hssp or sting  <cit> , or they can be generated by homolmapper at runtime as needed.
a summary of the available reference sequence choices for different scoring schemes is presented in table  <dig>
the available reference sequence methods for various homolmapper scoring schemes are shown.
gaps and insertions can be scored by either length or frequency , but the reference sequence is always the matched sequence.
"degen" and "sloppy" refer to different scoring algorithms using user-defined amino acid sets, as defined in the text.
reference methods are matched , user-chosen , and consensus.
some methods are independent of a reference sequence .
homolmapper can also use the segid field of the output pdb file to report a number of additional features.
the segid field can be used to display a consensus sequence, to show which residue in the structure is assigned to which user-defined amino acid set , or to show the amino acid numbers in the matched sequence corresponding to each residue in the structure.
the segid field is also used to report information about mutations, highlights, and multi-residue motifs.
implementation of mutations, residue highlights, and multi-residue motifs
homolmapper can process information about mutations, reporting the results to the segid field of the output pdb file.
mutations can be described via the command line or via an auxiliary text file supplied as an extra input.
mutations can simply be labeled on the structure, so that their probable location can be visualized to aid in interpretation, or they can be scored with a variety of algorithms.
for example, mutations can be scored by conservation of the wild-type residue found in the protein in which the mutation was described, by conservation of the mutant amino acid for substitutions, or by the percentage of sequences lacking amino acids after a given position for comparison to a c-terminal truncation.
homolmapper can also score different types of mutations by different algorithms  to provide a crude estimate of how well various mutations might be tolerated.
to provide a crude assessment of whether a given mutation might be tolerated, homolmapper can evaluate the alignment depending on the type of the mutation, as shown here.
scores are reported as percentages in the segid field of the output file.
the type of mutation is defined by the user as part of defining the mutation.
homolmapper can also use the mechanisms for mutation entry to input highlights and multi-residue motifs.
in highlighting, homolmapper will label the segid field of each residue in the structure aligned with an amino acid of a given type in a different sequence in the alignment.
this permits rapid visualization of where such residues would fall on the known structure, allowing assessment of potential surface accessibility, disulfide formation, or similar properties.
for multi-residue motifs, the user can list allowed amino acids at each position in the motif, and homolmapper will report the percentage of sequences in the alignment that meet all criteria to the segid field of each atom in each residue aligned with a position in the motif.
if more than one motif is specified, a 1– <dig> character motif identifier must be supplied to allow homolmapper to track which position belongs to which motif.
this motif identifier will be written to the element field of the output pdb file.
handling of subfamilies
homolmapper can also compare a single subfamily to the entire alignment, reporting the results of a single scoring scheme for the subfamily  and the entire msa .
subfamilies can be defined by the user either explicitly , implicitly , by pattern-matching to sequence names , or by a combination of these methods.
subfamily definitions can be supplied in a text file or via the command line.
it is also possible to use similar definition syntax to select a subset of the msa for discard, permitting the user to progress from a general analysis to a more specific examination of certain sequences without having to generate a new msa file.
in addition to permitting comparison of the subfamily to the entire msa, homolmapper can be used to search for residues or user-defined sets that are specific to the subfamily.
this is implemented by first locating positions where an allowed residue is present in a reference sequence within the subfamily, then summing the sequences within the subfamily that lack such an allowed residue.
if the resulting sum is below a user-controlled tolerance, sequences outside of the subfamily that possess an allowed residue at that position are summed and compared to a second tolerance.
only positions that are below the tolerance for both tests are reported.
if so requested, homolmapper can automatically search for all possible such residues and report any detected residues to segid while leaving other outputs free for other functions.
alternately, the user can designate the occupancy and/or b-factor to search for particular residues or residue sets of interest.
this method for detecting subfamily-specific residues has the advantage that it can be applied to small subfamilies or small alignments while retaining vestigial stringency by setting the tolerances to zero.
thus, for cases in which the total sample size is too small to be statistically valid, this approach nevertheless permits rapid detection of candidate residues for further characterization, for example by site-directed mutagenesis.
mutual information analysis
a challenge in analysis of any protein msa is the detection of coevolving or covarying residues: while highly conserved residues are often important for protein structure or function, variable residues that interact with each other are much harder to detect yet can nonetheless be functionally or structurally important.
the mutual information of pairs of positions in the msa has been applied as a general means of analyzing such positions  <cit> .
homolmapper can calculate mutual information for an msa by evaluating the joint entropies of all pairs of positions in the msa and then subtracting the joint entropy from the individual position entropies .
the resulting raw mutual-information scores can be normalized by the joint entropy  <cit>  or by the sum of the position entropies .
finally, scores are converted to z-scores for further analysis.
reporting the results of such analysis within the confines of the pdb format is difficult.
we have therefore adopted a compromise scheme whereby the maximum mutual information z-score is reported to b-factor for every residue, regardless of what that score is .
for residues having maximum z-scores above a threshold, the residue number associated with that score is reported to segid.
such residues are considered to be part of a mutually informative group, and the remaining outputs  are dedicated to describing that group.
the number of residues in that group is reported to element, and the sum of their residue numbers  is reported to occupancy.
thus, for a mutually informative pair with residue numbers  <dig> and  <dig>  element would be set to  <dig> and occupancy would be set to  <dig> .
this scheme allows residues that are part of overlapping groups to have similar occupancy values for visualization, and a full report of significant hits is also written out to a text file.
the time-consuming aspect of this analysis is the calculation of the joint-entropy matrix, but homolmapper will by default punch this matrix to a text file for reuse.
it is not possible to combine mutual information analysis with other scoring choices, because this scheme uses all of the current output fields.
using a pssm in lieu of an msa
homolmapper can also take a pssm as an input for users wishing to avoid the time involved in constructing an msa.
the pssm parsed by homolmapper is the ascii output pssm generated by psi-blast  <cit>  with the "-q" option.
scoring a pssm will always result in the consensus sequence being reported to the element field.
the segid can be used to report the information per position or the relative weight versus pseudocounts.
occupancy and b-factor can be used for charge, degen, or sloppy scoring as in scoring an msa, or they can be used for pssm-specific parameters such as the pssm value for the query sequence .
pssm inputs will always result in reporting the consensus residue to the element field.
the segid field can be used to report the information per position or the relative weight versus pseudocounts.
scores marked with an asterisk  are calculated by considering each row in the pssm as a 20-dimensional vector from the origin to the indicated point.
the query residue is then considered as a 20-dimensional unit vector normalized to the length of the pssm vector, and the distance and angle between the two vectors are calculated assuming the space is euclidean.
handling of non-canonical residues
many structures contain residues in addition to the canonical  <dig> amino acids familiar to all students of biochemistry.
such residues include amino acids such as phosphoserine  <cit> , arising from post-translational modification, and residues such as selenomethionine  <cit>  or diiodotyrosine  <cit> , arising from experimental manipulations.
moreover, proteins containing selenocysteine  or pyrrolysine  <cit>  effectively contain "extra" genetically encoded amino acids, as do proteins incorporating unnatural amino acids via modified trna techniques  <cit> .
non-standard residues may also appear in the alignment, due to sequencing ambiguity or due to the presence of noncanonical residues such as cse.
homolmapper is able to handle all of these cases.
by default, homolmapper will recognize five easily translated residues in pdb files and translate them to their genetically encoded equivalents: phosphoserine, phosphothreonine, phosphotyrosine, hydroxyproline, and selenomethionine are translated to ser, thr, tyr, pro, and met, respectively.
translation of other residues in pdb files is accomplished via an extra text file or command-line argument converting the three-letter residue code in the pdb file to one-letter codes found in the msa.
the use of a text file for this purpose permits the user to develop a library of non-standard residues from a number of structure files for repeated reuse.
homolmapper can also translate non-standard residues in the msa via a command-line flag.
such residues are again translated to one of the standard one-letter codes for matrix-based scoring schemes, although no such translation is necessary for scoring gaps, insertions, or identity.
this translation is handled via the command line because there is less standardization of such codes than is the case for noncanonical residues in pdb files.
handling of residues such as cse essentially involves expanding the set of amino acids parsed by homolmapper.
this is accomplished with a separate command-line flag expanding the parsed amino acid set in combination with a text file or command-line flag equating the pdb code for the residue in question with the new one-letter code for the "extra" amino acid.
there is no limit on the number of amino acids that can be added.
user extensibility
homolmapper offers a number of features designed to permit facile customization.
many of the more advanced features of homolmapper involve loading additional text files, so the user can readily maintain a library of frequently used accessory files, including run-settings files.
as discussed, it is also possible to import similarity scoring schemes at runtime.
such schemes are normally stored as pre-formatted python dictionaries that are loaded and compiled at runtime.
the homolmapper distribution includes a small utility that generates matrices in this format from user-supplied text files describing per-residue properties, making user generation of new schemes much faster and more reliable.
homolmapper can also import these schemes as plain text files.
homolmapper is controlled by flags specified on the command line.
such an interface normally requires the user to memorize the names of the flags that are relevant to their own work.
however, homolmapper permits the user to supply synonyms that can then be redefined by the application itself, so that the user can rename flags should they find their names difficult to remember.
such redefinitions can be done on the command line or via an accessory text file.
this file can then be referenced in a run-settings file for repeated reuse, permitting the user to use their own mnemonics.
documentation
homolmapper is distributed with examples of all the accessory input files .
each of these examples is heavily commented to aid in understanding the uses and formatting for the various files.
homolmapper also can generate considerable help information at runtime, via flags such as – help or – files.
the homolmapper script itself is heavily commented, although these comments are intended to aid in programming rather than use.
several small utilities are also included in this distribution.
in addition to the documentation distributed with homolmapper itself, a user guide is available as a separate download .
this pdf document provides demonstrations of many aspects of homolmapper operation with included structures and alignments, including both basic operations and more advanced applications such as working with expanded amino acid sets or mutual information analysis.
all required files are included with this distribution.
discussion
planned future development
development of homolmapper is an ongoing process.
improvements are planned in several aspects of program operation, including additional scoring schemes, acceptance of additional file formats for the msa, handling of multiple structural inputs, and greater flexibility in handling non-standard pdb files and in scoring pssm inputs.
the open architecture of the python implementation also facilitates distribution of user-suggested improvements to a wider user community.
techniques for comparison of multiple structures and subfamilies will eventually be incorporated as long-term improvements, and a dedicated gui is ultimately planned.
intended uses
homolmapper is well suited to general visualization of homology relationships, particularly in collaborative environments where different workers are using different molecular viewing programs.
it is also intended to aid in evaluation of candidate homology models, in visualizing the locations of mutations or motifs, and in comparison of a subfamily to an entire msa, including location of subfamily-specific residues.
homolmapper is thus a useful addition to the range of software permitting visualization of homology relationships in terms of protein structure.
CONCLUSIONS
earlier, partially functional versions of homolmapper have already proven useful for evaluating homology models  <cit>  and for examining homology and mutational information in a structural context  <cit> .
homolmapper is designed to permit some types of user customization with minimal effort and no programming.
homolmapper is distributed under a modified bsd to permit interested users to work with the program itself as desired.
it is particularly well suited to collaborations involving different molecular viewing environments.
extensive documentation is available, including many examples, and the homolmapper script itself is small and portable.
we anticipate that this application will prove a useful tool for workers investigating structure and function, structural modeling, and other fields suited to evaluation of protein sequence homology in a structural context.
availability and requirements
• project name: homolmapper
• project home page: homolmapper home page at the lagarias lab site, url:  .
also supplied with this manuscript as additional files.
• operating system: platform independent
• programming language: python
• other requirements: python  <dig>  or higher; standard python modules ; windows versions require the win <dig> extensions to python  for automated loading of scoring schemes.
• license: based on university of california bsd
• any restrictions to use by non-academics: yes
list of abbreviations
cse, selenocysteine
gui, graphical user interface
msa, multiple  sequence alignment
pdb file, protein data bank file format for protein structures  <cit>
pssm, position-specific scoring matrix
authors' contributions
ncr developed the software and wrote the documentation.
jcl aided in development and in drafting the manuscript.
both authors read and approved the final manuscript.
supplementary material
additional file 1
the standard homolmapper distribution , containing homolmapper itself and associated utilities and accessory files.
click here for file
additional file 2
alternative homolmapper distribution for operation as a batch file under windows, current as of march  <dig>
click here for file
additional file 3
additional documentation for homolmapper, including the pdf user guide and example structure, alignment, and accessory files, current as of march  <dig>
click here for file
acknowledgements
the authors wish to thank yong duan and hongxing lei for insightful collaboration on a homology modeling project that spurred development of homolmapper and shih-long tu and keenan taylor for its evaluation.
we also wish to thank the reviewers for their helpful suggestions.
this work was supported by a grant from the national institutes of health  to j.c.l.
and by a subcontract from the national science foundation center for biophotonics science and technology phy- <dig>

 the proliferation of known or suspected protein sequences in the post-genomic era and the slower, but steady, progress in protein structure determination implies that there are a large number of proteins with no experimentally determined structure but with varying homology to a protein of known structure. when such proteins are of experimental or practical interest, several approaches can be used to generate some form of approximate structural information to aid in the design or interpretation of biochemical experiments. for example, homology modeling can be used to build a model structure for the protein of interest based on the known structure. first introduced in, homology modeling has become a more commonly applied tool in recent years. however, homology modeling remains sensitive not only to the multiple sequence alignment of homologous proteins, but also to the particular algorithms used in the structural modeling. moreover, the confidence assigned to such models is dependent on the evolutionary relatedness of the modeling target to the known template. an alternative approach is to map information from the msa onto the known structure, typically via color-coding or similar visual procedures. such combinations of structural and sequence information do not contain as much information as carefully made homology models, but they permit many of the same applications as homology modeling, such as predicting the location and/or function of potentially interesting residues, and are also useful in evaluating and modifying homology models themselves: a homology model that places a site of frequent gaps and insertions in the middle of a central beta strand rather than on a surface loop is unlikely to be reliable. scoring the msa onto the known structure is driven only by the msa, without potential bias from the modeling or threading programs. this approach was formalized in with pdbalign, a command-line application taking as inputs a protein structure in pdb format and an msa in gcg format. pdbalign generates a new pdb file retaining the original sequence and spatial information, but with homology information written to the b factor field of the output pdb file. scoring schemes cannot be added to pdbalign without changing the source code and recompiling, and the program is similarly limited in its ability to handle residues other than the canonical amino acids without manual editing of the pdb file. in the years since the appearance of pdbalign, a number of other programs have been developed that permit such evaluation of sequence information in various contexts, including swissmodel, chimera, protein explorer, consurf, sting, and several commercial packages. most recently, multiseq has been reported as an extension to the popular vmd structural analysis software with an emphasis on evolutionary relationships. the underlying trend in more recent software is therefore to tie presentation of information from the msa to a single viewing environment, such as chimera or vmd. such software is thus not well suited to collaborations among workers who prefer different environments and may not be well-suited to automated operation because of the emphasis on integration with a viewing and analysis package or web server largely driven by a graphical user interface. therefore, we believe there is a niche for a flexible, up-to-date, open-source command-line tool for mapping the homology information from protein sequence alignments onto protein structures. we have developed homolmapper as a command-line python application for such work. homolmapper places special emphasis on visualizing additional information such as the location of mutations, on defining and characterizing a subfamily within a given alignment, and on allowing runtime extensibility for user-defined scoring schemes and for handling of noncanonical residues in the structure and/or alignment. homolmapper currently uses pdb files and several different msa formats as inputs and outputs a new pdb file with homology information written to fields that do not change the spatial information. this permits the user to view the results in the viewing environment of their own choice. it is also possible to use a position-specific scoring matrix generated by psi-blast instead of an msa. homolmapper is small, portable, and requires only a working python installation of version or later. implementation and  rationale for program operation within a given pdb file, individual atoms are assigned a single atom or hetatm record identifying the atom and locating it within a 3-dimensional cartesian coordinate system. within such records, individual fields such as residue number, atom name, and z coordinate are defined by column offset. the pdb format also provides several additional fields that provide either additional experimental detail about the structure determination or provide additional descriptive information. b factor has been previously used as a convenient field for storing information about homology. like b field, occupancy is a 6-column floating-point column well suited to storing such information; the other fields dispensable for unique specification of the atom name and location are smaller and are less frequently supported by viewing programs. homolmapper writes information to occupancy and/or b factor; additional outputs are written to the segid field, albeit with less precision. the element field can also be used. the primary output is a new pdb file to permit the user to evaluate the results in the viewing program of choice. of course, this imposes fundamental limitations on the nature of the outputs, because they must fit the pdb standard. homolmapper results also must be archived as complete structure files rather than simple parameter lists, although the extra storage requirements are modest and such files are by their nature stand-alone and not linked to a single "master" structure file. homolmapper can also report scores as a tab-delimited text file for analysis with other software tools. overall architecture homolmapper is written in python using a functional approach and has an overall layout resembling a c program. extensive commenting is provided within the main script for users wishing to alter the program itself, but such editing is not needed for normal operations nor for many types of user customization. homolmapper is a strictly command-line application; user control is provided via a large number of flags that can be added to the command line to control various aspects of program behavior. homolmapper can also use specialized text files to import information on a number of options, such as subfamilies, mutations, non-standard residues, and additional scoring schemes. it is possible to supply some or all of the desired settings, including input files, in a text file for repetitive tasks or to supply preferred settings. this feature also aids in automation of homolmapper for batch jobs. homolmapper can also generate such settings files, as well as generating files containing the subfamily definition, protein sequences from the input pdb file, or runtime alignment. homolmapper output files have headers indicating their source; most provide basic information about the run parameters used in preparing the file. matching the structure to the alignment to produce meaningful output, software such as homolmapper must synchronize the protein structure and the msa by matching the sequence contained in the protein structure to a sequence in the msa. in homolmapper, this matching process is by default automatic. homolmapper will first check for exact matches to the entire structure sequence and then, assuming no matches were found, for exact matches to each chain in the pdb file. if no significant matches are found at this point, the sequence in each chain will be broken into short blocks, and exact matches to those blocks will be used to match the sequence. should this fail, a slower recursive algorithm will be employed. if no significant matches can be found, an error will be triggered and execution will cease. the chosen matched sequence is used to determine which portions of the structure are exact matches to the msa; only these residues will be scored, so that the presence of exogenous sequence such as a his tag will not result in spurious results. by default, homolmapper will pass all unscored atoms to the output file without changes, but it is possible to set the output fields of unscored atoms to zero or to empty fields if so requested. the user has control over several aspects of this process. it is possible to choose the first matching method used, so that methods can be skipped if so chosen. it is also possible to redefine the threshold of significance for the entire matched sequence, to specify the size of the peptide blocks used at the third step, and to specify the smallest significant fragments used by the recursive algorithm. additionally, the user can supply the name of one of the sequences in the msa. if such a name is supplied and matches a name in the msa, homolmapper will only test that name as a significant match. if an invalid name is supplied, homolmapper will warn the user and use the default method. scoring schemes and reference sequences homolmapper can score sequences by gaps, insertions, identity, shannon's entropy, information content, and several similarity schemes. shannon's entropy and information content can also use user-defined amino acid sets, which readily permits correction for chemical similarity among residues in entropy scoring. these schemes are by default reported in bits, but the user can choose an alternative base for the logarithm. rather than trying to use a single objective function for scoring the msa including gaps, homolmapper uses separate analysis of gaps and insertion. this reflects its intended uses in analyzing homology models and in structure/function studies, because gaps and insertions are useful in evaluating the overall correctness of fold in homology modeling with distant templates. the elongation of surface loops has also been implicated in cold adaptation of enzymes from psychrophilic organisms. gaps are here defined as positions where the matched sequence lacks amino acids but other proteins in the alignment have them, and insertions are defined as positions where the matched sequence has amino acids but at least one other protein lacks them. gaps and insertions are therefore always scored relative to the matched sequence. gaps and insertions can be scored by length or by frequency. homolmapper offers several approaches for calculating similarity of amino acids. identity can be calculated by a simple arithmetic procedure. this procedure compares each residue in the alignment to the aligned residue in a reference sequence, and the number of identical residues will be divided by the total number of sequences in the alignment. alternately, the number of identical residues can be divided by the number of sequences that have a residue at the position in question to avoid penalizing for gaps, which can be useful for locating rare but conserved insertions. several types of similarity can be calculated via a matrix lookup procedure which makes it easy to add scoring schemes by importing them as text files at runtime. blosum, pam, and charge matrices are incorporated into the homolmapper script itself. a total of other scoring schemes are supplied as formatted text files as part of the homolmapper distribution, including series of blosum, pam, and gonnet substitution matrices and additional scoring matrices based on physical properties such as hydrophobicity, sidechain entropy of folding, and nonpolar accessible surface area. any or all of these schemes can be imported at runtime as needed, although homolmapper will use at most two such schemes because of the limited number of output fields available. homolmapper can report both the score and the variation at each position for any matrix scheme, permitting assessment of both conservation and variability. variation can be reported as standard deviation or standard error of the scores at each position in the msa, or as the range of scores spanned at each position. homolmapper also reports mean, standard deviation, and score diversity for the scores themselves in the header of the output pdb file. score diversity is here calculated as the percentage of the maximum shannon entropy for the score in question, and is therefore akin to the dops measure used in assessing alignment scoring in scorecons. scoring schemes can also be reported as z-scores relative to the calculated mean and standard deviation. three substitution matrices are built-in to the homolmapper application, while the others are supplied as external matrices that can be loaded at runtime if so desired. some of the external matrices are supplied in a compressed archive, while others are not. the expanded blosum and pam schemes incorporate standard values for'b,''x,' and'z' amino acids. in addition to identity and the matrix-lookup schemes, homolmapper can score using user-defined amino acid sets. such sets treat a group of amino acids as equivalent for scoring. homolmapper can report the percentage of sequences having a member of such a set at each position in the structure, or it can define all amino acids as belonging to sets and then report the percentage of sequences having members of the same set as a reference sequence for each position. this feature gives the user the ability to quickly look for features such as hydrogen bond donors at an unusual ph without taking the time to create a suitable scoring matrix. it is possible to disable gap penalties for scoring by matrix-lookup and by user-defined amino acid sets. several of these scoring schemes are relative. for example, calculating percent identity implies the existence of a reference sequence to which the others will be compared. by default, homolmapper uses the matched sequence as the reference sequence; as discussed above, this is always the case for scoring gaps or insertions. however, schemes such as identity or similarity matrices can instead use a consensus sequence or a different sequence found in the alignment as the reference sequence. consensus sequences can be supplied as part of the input msa, permitting import of consensus sequences from sources such as hssp or sting, or they can be generated by homolmapper at runtime as needed. a summary of the available reference sequence choices for different scoring schemes is presented in table the available reference sequence methods for various homolmapper scoring schemes are shown. gaps and insertions can be scored by either length or frequency, but the reference sequence is always the matched sequence. "degen" and "sloppy" refer to different scoring algorithms using user-defined amino acid sets, as defined in the text. reference methods are matched, user-chosen, and consensus. some methods are independent of a reference sequence. homolmapper can also use the segid field of the output pdb file to report a number of additional features. the segid field can be used to display a consensus sequence, to show which residue in the structure is assigned to which user-defined amino acid set, or to show the amino acid numbers in the matched sequence corresponding to each residue in the structure. the segid field is also used to report information about mutations, highlights, and multi-residue motifs. implementation of mutations, residue highlights, and multi-residue motifs homolmapper can process information about mutations, reporting the results to the segid field of the output pdb file. mutations can be described via the command line or via an auxiliary text file supplied as an extra input. mutations can simply be labeled on the structure, so that their probable location can be visualized to aid in interpretation, or they can be scored with a variety of algorithms. for example, mutations can be scored by conservation of the wild-type residue found in the protein in which the mutation was described, by conservation of the mutant amino acid for substitutions, or by the percentage of sequences lacking amino acids after a given position for comparison to a c-terminal truncation. homolmapper can also score different types of mutations by different algorithms to provide a crude estimate of how well various mutations might be tolerated. to provide a crude assessment of whether a given mutation might be tolerated, homolmapper can evaluate the alignment depending on the type of the mutation, as shown here. scores are reported as percentages in the segid field of the output file. the type of mutation is defined by the user as part of defining the mutation. homolmapper can also use the mechanisms for mutation entry to input highlights and multi-residue motifs. in highlighting, homolmapper will label the segid field of each residue in the structure aligned with an amino acid of a given type in a different sequence in the alignment. this permits rapid visualization of where such residues would fall on the known structure, allowing assessment of potential surface accessibility, disulfide formation, or similar properties. for multi-residue motifs, the user can list allowed amino acids at each position in the motif, and homolmapper will report the percentage of sequences in the alignment that meet all criteria to the segid field of each atom in each residue aligned with a position in the motif. if more than one motif is specified, a 1– character motif identifier must be supplied to allow homolmapper to track which position belongs to which motif. this motif identifier will be written to the element field of the output pdb file. handling of subfamilies homolmapper can also compare a single subfamily to the entire alignment, reporting the results of a single scoring scheme for the subfamily and the entire msa. subfamilies can be defined by the user either explicitly, implicitly, by pattern-matching to sequence names, or by a combination of these methods. subfamily definitions can be supplied in a text file or via the command line. it is also possible to use similar definition syntax to select a subset of the msa for discard, permitting the user to progress from a general analysis to a more specific examination of certain sequences without having to generate a new msa file. in addition to permitting comparison of the subfamily to the entire msa, homolmapper can be used to search for residues or user-defined sets that are specific to the subfamily. this is implemented by first locating positions where an allowed residue is present in a reference sequence within the subfamily, then summing the sequences within the subfamily that lack such an allowed residue. if the resulting sum is below a user-controlled tolerance, sequences outside of the subfamily that possess an allowed residue at that position are summed and compared to a second tolerance. only positions that are below the tolerance for both tests are reported. if so requested, homolmapper can automatically search for all possible such residues and report any detected residues to segid while leaving other outputs free for other functions. alternately, the user can designate the occupancy and/or b-factor to search for particular residues or residue sets of interest. this method for detecting subfamily-specific residues has the advantage that it can be applied to small subfamilies or small alignments while retaining vestigial stringency by setting the tolerances to zero. thus, for cases in which the total sample size is too small to be statistically valid, this approach nevertheless permits rapid detection of candidate residues for further characterization, for example by site-directed mutagenesis. mutual information analysis a challenge in analysis of any protein msa is the detection of coevolving or covarying residues: while highly conserved residues are often important for protein structure or function, variable residues that interact with each other are much harder to detect yet can nonetheless be functionally or structurally important. the mutual information of pairs of positions in the msa has been applied as a general means of analyzing such positions. homolmapper can calculate mutual information for an msa by evaluating the joint entropies of all pairs of positions in the msa and then subtracting the joint entropy from the individual position entropies. the resulting raw mutual-information scores can be normalized by the joint entropy or by the sum of the position entropies. finally, scores are converted to z-scores for further analysis. reporting the results of such analysis within the confines of the pdb format is difficult. we have therefore adopted a compromise scheme whereby the maximum mutual information z-score is reported to b-factor for every residue, regardless of what that score is. for residues having maximum z-scores above a threshold, the residue number associated with that score is reported to segid. such residues are considered to be part of a mutually informative group, and the remaining outputs are dedicated to describing that group. the number of residues in that group is reported to element, and the sum of their residue numbers is reported to occupancy. thus, for a mutually informative pair with residue numbers and element would be set to and occupancy would be set to. this scheme allows residues that are part of overlapping groups to have similar occupancy values for visualization, and a full report of significant hits is also written out to a text file. the time-consuming aspect of this analysis is the calculation of the joint-entropy matrix, but homolmapper will by default punch this matrix to a text file for reuse. it is not possible to combine mutual information analysis with other scoring choices, because this scheme uses all of the current output fields. using a pssm in lieu of an msa homolmapper can also take a pssm as an input for users wishing to avoid the time involved in constructing an msa. the pssm parsed by homolmapper is the ascii output pssm generated by psi-blast with the "-q" option. scoring a pssm will always result in the consensus sequence being reported to the element field. the segid can be used to report the information per position or the relative weight versus pseudocounts. occupancy and b-factor can be used for charge, degen, or sloppy scoring as in scoring an msa, or they can be used for pssm-specific parameters such as the pssm value for the query sequence. pssm inputs will always result in reporting the consensus residue to the element field. the segid field can be used to report the information per position or the relative weight versus pseudocounts. scores marked with an asterisk are calculated by considering each row in the pssm as a 20-dimensional vector from the origin to the indicated point. the query residue is then considered as a 20-dimensional unit vector normalized to the length of the pssm vector, and the distance and angle between the two vectors are calculated assuming the space is euclidean. handling of non-canonical residues many structures contain residues in addition to the canonical amino acids familiar to all students of biochemistry. such residues include amino acids such as phosphoserine, arising from post-translational modification, and residues such as selenomethionine or diiodotyrosine, arising from experimental manipulations. moreover, proteins containing selenocysteine or pyrrolysine effectively contain "extra" genetically encoded amino acids, as do proteins incorporating unnatural amino acids via modified trna techniques. non-standard residues may also appear in the alignment, due to sequencing ambiguity or due to the presence of noncanonical residues such as cse. homolmapper is able to handle all of these cases. by default, homolmapper will recognize five easily translated residues in pdb files and translate them to their genetically encoded equivalents: phosphoserine, phosphothreonine, phosphotyrosine, hydroxyproline, and selenomethionine are translated to ser, thr, tyr, pro, and met, respectively. translation of other residues in pdb files is accomplished via an extra text file or command-line argument converting the three-letter residue code in the pdb file to one-letter codes found in the msa. the use of a text file for this purpose permits the user to develop a library of non-standard residues from a number of structure files for repeated reuse. homolmapper can also translate non-standard residues in the msa via a command-line flag. such residues are again translated to one of the standard one-letter codes for matrix-based scoring schemes, although no such translation is necessary for scoring gaps, insertions, or identity. this translation is handled via the command line because there is less standardization of such codes than is the case for noncanonical residues in pdb files. handling of residues such as cse essentially involves expanding the set of amino acids parsed by homolmapper. this is accomplished with a separate command-line flag expanding the parsed amino acid set in combination with a text file or command-line flag equating the pdb code for the residue in question with the new one-letter code for the "extra" amino acid. there is no limit on the number of amino acids that can be added. user extensibility homolmapper offers a number of features designed to permit facile customization. many of the more advanced features of homolmapper involve loading additional text files, so the user can readily maintain a library of frequently used accessory files, including run-settings files. as discussed, it is also possible to import similarity scoring schemes at runtime. such schemes are normally stored as pre-formatted python dictionaries that are loaded and compiled at runtime. the homolmapper distribution includes a small utility that generates matrices in this format from user-supplied text files describing per-residue properties, making user generation of new schemes much faster and more reliable. homolmapper can also import these schemes as plain text files. homolmapper is controlled by flags specified on the command line. such an interface normally requires the user to memorize the names of the flags that are relevant to their own work. however, homolmapper permits the user to supply synonyms that can then be redefined by the application itself, so that the user can rename flags should they find their names difficult to remember. such redefinitions can be done on the command line or via an accessory text file. this file can then be referenced in a run-settings file for repeated reuse, permitting the user to use their own mnemonics. documentation homolmapper is distributed with examples of all the accessory input files. each of these examples is heavily commented to aid in understanding the uses and formatting for the various files. homolmapper also can generate considerable help information at runtime, via flags such as – help or – files. the homolmapper script itself is heavily commented, although these comments are intended to aid in programming rather than use. several small utilities are also included in this distribution. in addition to the documentation distributed with homolmapper itself, a user guide is available as a separate download. this pdf document provides demonstrations of many aspects of homolmapper operation with included structures and alignments, including both basic operations and more advanced applications such as working with expanded amino acid sets or mutual information analysis. all required files are included with this distribution. discussion planned future development development of homolmapper is an ongoing process. improvements are planned in several aspects of program operation, including additional scoring schemes, acceptance of additional file formats for the msa, handling of multiple structural inputs, and greater flexibility in handling non-standard pdb files and in scoring pssm inputs. the open architecture of the python implementation also facilitates distribution of user-suggested improvements to a wider user community. techniques for comparison of multiple structures and subfamilies will eventually be incorporated as long-term improvements, and a dedicated gui is ultimately planned. intended uses homolmapper is well suited to general visualization of homology relationships, particularly in collaborative environments where different workers are using different molecular viewing programs. it is also intended to aid in evaluation of candidate homology models, in visualizing the locations of mutations or motifs, and in comparison of a subfamily to an entire msa, including location of subfamily-specific residues. homolmapper is thus a useful addition to the range of software permitting visualization of homology relationships in terms of protein structure.  earlier, partially functional versions of homolmapper have already proven useful for evaluating homology models and for examining homology and mutational information in a structural context. homolmapper is designed to permit some types of user customization with minimal effort and no programming. homolmapper is distributed under a modified bsd to permit interested users to work with the program itself as desired. it is particularly well suited to collaborations involving different molecular viewing environments. extensive documentation is available, including many examples, and the homolmapper script itself is small and portable. we anticipate that this application will prove a useful tool for workers investigating structure and function, structural modeling, and other fields suited to evaluation of protein sequence homology in a structural context. availability and requirements • project name: homolmapper • project home page: homolmapper home page at the lagarias lab site, url:. also supplied with this manuscript as additional files. • operating system: platform independent • programming language: python • other requirements: python or higher; standard python modules; windows versions require the win extensions to python for automated loading of scoring schemes. • license: based on university of california bsd • any restrictions to use by non-academics: yes list of abbreviations cse, selenocysteine gui, graphical user interface msa, multiple sequence alignment pdb file, protein data bank file format for protein structures pssm, position-specific scoring matrix authors' contributions ncr developed the software and wrote the documentation. jcl aided in development and in drafting the manuscript. both authors read and approved the final manuscript. supplementary material additional file 1 the standard homolmapper distribution, containing homolmapper itself and associated utilities and accessory files. click here for file additional file 2 alternative homolmapper distribution for operation as a batch file under windows, current as of march click here for file additional file 3 additional documentation for homolmapper, including the pdf user guide and example structure, alignment, and accessory files, current as of march click here for file acknowledgements the authors wish to thank yong duan and hongxing lei for insightful collaboration on a homology modeling project that spurred development of homolmapper and shih-long tu and keenan taylor for its evaluation. we also wish to thank the reviewers for their helpful suggestions. this work was supported by a grant from the national institutes of health to j.c.l. and by a subcontract from the national science foundation center for biophotonics science and technology phy- 
we describe homolmapper, a command-line application for mapping information from a multiple protein sequence alignment onto a protein structure for analysis in the viewing software of the user's choice. homolmapper also provides tools for defining and analyzing subfamilies relative to a larger alignment, for mutual information analysis, and for rapidly visualizing the locations of mutations and multi-residue motifs. most recent software implementations for such analysis are tied to specific molecular viewing programs, which can be problematic for collaborations involving multiple viewing environments. homolmapper is a useful tool for analysis of homology relationships among proteins in a structural context. over the past decade, a number of tools have emerged for the examination of homology relationships among protein sequences in a structural context.
 over the past decade, a number of tools have emerged for the examination of homology relationships among protein sequences in a structural context. most recent software implementations for such analysis are tied to specific molecular viewing programs, which can be problematic for collaborations involving multiple viewing environments. incorporation into larger packages also adds complications for users interested in adding their own scoring schemes or in analyzing proteins incorporating unusual amino acid residues such as selenocysteine.  we describe homolmapper, a command-line application for mapping information from a multiple protein sequence alignment onto a protein structure for analysis in the viewing software of the user's choice. homolmapper is small and is written in python to ensure portability. it is released for non-commercial use under a modified university of california bsd license. homolmapper permits facile import of additional scoring schemes and can incorporate arbitrary additional amino acids to allow handling of residues such as selenocysteine or pyrrolysine. homolmapper also provides tools for defining and analyzing subfamilies relative to a larger alignment, for mutual information analysis, and for rapidly visualizing the locations of mutations and multi-residue motifs.  homolmapper is a useful tool for analysis of homology relationships among proteins in a structural context. there is also extensive, example-driven documentation available. more information about homolmapper is available at. 