BACKGROUND
expressed proteins provide experimental evidence that genes in the genome are being transcribed and translated to produce a protein product.
recently, a new structural genome annotation method, proteogenomic mapping, has been developed that uses identified peptides from experimentally derived proteomics data to identify functional elements in genomes and to improve genome annotation  <cit> .
initially used for the structural annotation of prokaryotic genomes, proteogenomic mapping is rapidly gaining traction in eukaryotic genome annotation projects with larger genomes as a complementary method  <cit> .
proteogenomic mapping can identify potential new genes or corrections to the boundaries of predicted genes by using peptide matches against the genome that do not match against the predicted proteome to generate expressed protein sequence tags   <cit> .
when aligned with the genome and combined with the published structural annotation, these epsts are indicative of translation throughout the genome and can serve to supplement traditional structural genome annotation methods  <cit> .
while a number of research groups are becoming increasingly active in the field of proteogenomic mapping  <cit> , there is a lack of published and standardized tools to rapidly and exactly map identified peptides back to the genome translated in all  <dig> reading frames.
to our knowledge, there is only one comparable tool, pepline  <cit> , which utilizes a de novo based spectral identification methodology.
in contrast our tool is implemented to work with the output from lc ms/ms combined with database search based spectral identification algorithms.
pepline uses peptide sequence tags , short spectral match translations of 3- <dig> amino acids with flanking matches on either end for searches against the genome, where our tool works with peptides derived from ms/ms databases searches.
while pepline's use of psts allows the direct searching of spectra against the genome, a staged search method of searching spectra identified against database searches is an alternative.
implementation
the proteogenomic mapping pipeline is free to obtain and use, written completely in java, and available for all common computer platforms.
it is licensed under the gnu gplv <dig> license making it completely open source and making the source code and implementation methodology available to the end user  <cit> .
we have endeavored to make this tool as easy to use as possible and have provided both a command line version and a graphical user interface  for all common platforms.
data input and customization
the gui is shown in figure  <dig> and takes as input from the user  <dig> files: a fasta file of the peptides to be searched, a fasta file containing the nucleic acid sequences the peptides are to be mapped against , and a file containing the genetic code to use based on the format of the national center for biotechnology information's  toolkit for genetic codes  <cit> .
furthermore, fasta output from the splice site prediction tool genesplicer  <cit>  can optionally be provided.
if present, the splice sites given in that file are used instead of the default splice sites.
the user is also required to provide a file name and location for the three output files that will be generated.
to generate the fasta file of the peptides to be searched, it is expected that the user will have performed spectral matching for their ms dataset of interest against databases generated from both the proteome and the genome translated in all six reading frames and confirm these peptide identifications using a peptide validation strategy.
after validation, the unique peptide identifications resulting from a database search against the genome that are not contained among the proteome peptide identifications should be used as the list of peptides to be searched.
the command line version of the proteogenomic mapping pipeline allows the same inputs as the gui to be specified as command line arguments and can be run on standard computer platforms .
an example of using the command line version of the program is included in the readme file provided with the application.
the application translates the nucleotide database to protein in all  <dig> reading frames using the genetic code selected by the user  and maps the peptides to the translated genome using the aho-corasick string searching algorithm to provide rapid and exact matches of peptides to the genome  <cit> .
the aho-corasick string matching algorithm  <cit>  quickly locates all occurrences of keywords within a text string.
the algorithm consists primarily of two phases.
in the first, a finite state machine is constructed from the set of keywords.
the time to construct this machine and its memory requirements are linearly proportional to the sum of the lengths of the keywords.
the second phase consists of running the state machine using the text string as input.
this phase takes time linearly proportional to the length of the text string.
thus, the time to run the entire algorithm is proportional to the sum of the length of the keywords and the length of the text string.
in our case, the peptides for which to search are the keywords, and the reference genome against which to search is the text string.
epst generation
once a peptide has been mapped to a nucleotide sequence, the reverse translated peptide is used to create an expressed protein sequence tag   <cit> .
figure  <dig> illustrates the epst generation process for prokaryotes and figure  <dig> shows both options for the epst generation process in eukaryotes.
for prokaryotes, the reverse translated peptide is extended in the 3' direction to an in-frame stop codon.
in the 5' direction, the first in-frame stop-codon upstream of the peptide  is identified and the peptide is extended to the first in-frame start downstream from this 5' stop before the start of the peptide.
in the case that no in-frame start occurs between the 5' stop and the start of the peptide, the start of the peptide is used as the start of the epst.
the process is more complex for eukaryotes due to splicing.
for eukaryotes, the peptides can be extended to produce epsts using three different approaches.
in the first approach, the peptide is extended downstream to the first in-frame stop or splice site signal  <cit>  and upstream until the first in-frame start, in-frame stop, or splice site signal.
we have found that this approach often generates epsts that are far longer than typical exons.
we speculate that this is because the potential new orfs identified by this approach do not have a canonical splice site signal.
while the application does default to using canonical splice site signals, our second approach includes the option of using predictions from genesplicer  <cit> , a computational splice site prediction tool, by allowing the user to select to input genesplicer output for use instead of the canonical splice site signals.
a third option is to extend the peptide upstream and downstream by a nucleotide length to be specified by the user.
output file description
three output files are produced by the application.
the first file is a fasta file containing the epsts generated for the dataset.
the second file is a more detailed tab separated text file containing the original peptide's identification, the peptide sequence, the fasta header for the nucleotide sequence containing the match, the mapping start and end locations for the reverse translated peptide, the strand the nucleotide match, the reading frame of the match, the reverse translated peptide sequence, a longer nucleotide sequence extending from the 5' in-frame stop codon immediately upstream of the peptide to the 3' in-frame stop codon immediately downstream of the peptide, the epst nucleotide sequence and the start and stop locations of the epst on the nucleotide sequence, the length of the epst, and the translated epst.
the third file is a gff <dig> file containing the epsts generated for the dataset to provide researchers with a file format they can quickly load into genome browsers for data visualization.
example datasets
to test our implementation we acquired previously published proteogenomic mapping datasets for a number of organisms.
for a relatively small example data set, we selected a proteogenomic mapping dataset for the channel catfish virus  <cit> .
this small dataset contains  <dig> unique peptide identifications, of which  <dig> peptides did not map to the predicted proteome of the virus, but do map to novel open reading frames in the viral genome, and expression of several of these genes was confirmed by rt-pcr.
our example dataset consists of a fasta file of these  <dig> peptides and the reference genome  for the channel catfish virus.
for bacterial examples, proteomics datasets from three different microorganisms  <cit>  were used to test our application.
for a eukaryotic example, a previously published proteomics dataset generated from chicken serum was utilized for testing  <cit> .
table  <dig> details the number of unique peptides and the number of unique peptides mapping uniquely to the genomic database search contained in each of these five datasets.
RESULTS
the output from the proteogenomic mapping pipeline matches the previously published results against our test dataset  <cit> , and our output provides additional information that not only places the mapped peptides on the appropriate nucleotide strand but also includes the reading frame in which the match occurs.
table  <dig> gives a list of the peptides and corresponding epsts for this dataset.
we have also successfully tested this tool for proteogenomic mapping in previously published bacterial  <cit>  and eukaryotic datasets  <cit> .
table  <dig> provides runtime analysis for each of our five test datasets, and demonstrates that the proteogenomic mapping tool scales well for increasingly large datasets.
possible future updates to this application include parallelization of the searches against the genome in all  <dig> reading frames, and the introduction of better thread support to improve performance further on today's modern increasingly multi-core processors.
CONCLUSIONS
the proteogenomic mapping pipeline provides a standalone tool that facilitates a streamlined mapping of peptides to a target genome for structurally genome annotation through the use of proteomics.
this software can be used on a variety of current operating systems and is its ability to use a variety of genetic codes makes it easily customizable for researchers performing proteogenomic mapping in a variety of prokaryotes, eukaryotes, and viruses.
availability and requirements
project name: the proteogenomic mapping pipeline
project home page: http://www.agbase.msstate.edu/tools/pgm/
operating system: windows xp, vista , vista, linux, macos
programming languages: java
other requirements: java
license: gnu gplv <dig>  <cit>
any restrictions to use by non-academics: none
authors' contributions
fmm and scb developed the initial procedure for generating epsts.
bn and ml developed the algorithms for generating epsts for prokaryotes.
smb and nw designed the pipeline and nw implemented the initial perl version of the pipeline.
wss and bmm implemented the current java version and the graphical user interface.
ysd implemented the string matching module.
wss and smb drafted the document.
bmm developed the software documentation.
all authors read and approved the final manuscript.

 expressed proteins provide experimental evidence that genes in the genome are being transcribed and translated to produce a protein product. recently, a new structural genome annotation method, proteogenomic mapping, has been developed that uses identified peptides from experimentally derived proteomics data to identify functional elements in genomes and to improve genome annotation. initially used for the structural annotation of prokaryotic genomes, proteogenomic mapping is rapidly gaining traction in eukaryotic genome annotation projects with larger genomes as a complementary method. proteogenomic mapping can identify potential new genes or corrections to the boundaries of predicted genes by using peptide matches against the genome that do not match against the predicted proteome to generate expressed protein sequence tags. when aligned with the genome and combined with the published structural annotation, these epsts are indicative of translation throughout the genome and can serve to supplement traditional structural genome annotation methods. while a number of research groups are becoming increasingly active in the field of proteogenomic mapping, there is a lack of published and standardized tools to rapidly and exactly map identified peptides back to the genome translated in all reading frames. to our knowledge, there is only one comparable tool, pepline, which utilizes a de novo based spectral identification methodology. in contrast our tool is implemented to work with the output from lc ms/ms combined with database search based spectral identification algorithms. pepline uses peptide sequence tags, short spectral match translations of 3- amino acids with flanking matches on either end for searches against the genome, where our tool works with peptides derived from ms/ms databases searches. while pepline's use of psts allows the direct searching of spectra against the genome, a staged search method of searching spectra identified against database searches is an alternative. implementation the proteogenomic mapping pipeline is free to obtain and use, written completely in java, and available for all common computer platforms. it is licensed under the gnu gplv license making it completely open source and making the source code and implementation methodology available to the end user. we have endeavored to make this tool as easy to use as possible and have provided both a command line version and a graphical user interface for all common platforms. data input and customization the gui is shown in figure and takes as input from the user files: a fasta file of the peptides to be searched, a fasta file containing the nucleic acid sequences the peptides are to be mapped against, and a file containing the genetic code to use based on the format of the national center for biotechnology information's toolkit for genetic codes. furthermore, fasta output from the splice site prediction tool genesplicer can optionally be provided. if present, the splice sites given in that file are used instead of the default splice sites. the user is also required to provide a file name and location for the three output files that will be generated. to generate the fasta file of the peptides to be searched, it is expected that the user will have performed spectral matching for their ms dataset of interest against databases generated from both the proteome and the genome translated in all six reading frames and confirm these peptide identifications using a peptide validation strategy. after validation, the unique peptide identifications resulting from a database search against the genome that are not contained among the proteome peptide identifications should be used as the list of peptides to be searched. the command line version of the proteogenomic mapping pipeline allows the same inputs as the gui to be specified as command line arguments and can be run on standard computer platforms. an example of using the command line version of the program is included in the readme file provided with the application. the application translates the nucleotide database to protein in all reading frames using the genetic code selected by the user and maps the peptides to the translated genome using the aho-corasick string searching algorithm to provide rapid and exact matches of peptides to the genome. the aho-corasick string matching algorithm quickly locates all occurrences of keywords within a text string. the algorithm consists primarily of two phases. in the first, a finite state machine is constructed from the set of keywords. the time to construct this machine and its memory requirements are linearly proportional to the sum of the lengths of the keywords. the second phase consists of running the state machine using the text string as input. this phase takes time linearly proportional to the length of the text string. thus, the time to run the entire algorithm is proportional to the sum of the length of the keywords and the length of the text string. in our case, the peptides for which to search are the keywords, and the reference genome against which to search is the text string. epst generation once a peptide has been mapped to a nucleotide sequence, the reverse translated peptide is used to create an expressed protein sequence tag. figure illustrates the epst generation process for prokaryotes and figure shows both options for the epst generation process in eukaryotes. for prokaryotes, the reverse translated peptide is extended in the 3' direction to an in-frame stop codon. in the 5' direction, the first in-frame stop-codon upstream of the peptide is identified and the peptide is extended to the first in-frame start downstream from this 5' stop before the start of the peptide. in the case that no in-frame start occurs between the 5' stop and the start of the peptide, the start of the peptide is used as the start of the epst. the process is more complex for eukaryotes due to splicing. for eukaryotes, the peptides can be extended to produce epsts using three different approaches. in the first approach, the peptide is extended downstream to the first in-frame stop or splice site signal and upstream until the first in-frame start, in-frame stop, or splice site signal. we have found that this approach often generates epsts that are far longer than typical exons. we speculate that this is because the potential new orfs identified by this approach do not have a canonical splice site signal. while the application does default to using canonical splice site signals, our second approach includes the option of using predictions from genesplicer, a computational splice site prediction tool, by allowing the user to select to input genesplicer output for use instead of the canonical splice site signals. a third option is to extend the peptide upstream and downstream by a nucleotide length to be specified by the user. output file description three output files are produced by the application. the first file is a fasta file containing the epsts generated for the dataset. the second file is a more detailed tab separated text file containing the original peptide's identification, the peptide sequence, the fasta header for the nucleotide sequence containing the match, the mapping start and end locations for the reverse translated peptide, the strand the nucleotide match, the reading frame of the match, the reverse translated peptide sequence, a longer nucleotide sequence extending from the 5' in-frame stop codon immediately upstream of the peptide to the 3' in-frame stop codon immediately downstream of the peptide, the epst nucleotide sequence and the start and stop locations of the epst on the nucleotide sequence, the length of the epst, and the translated epst. the third file is a gff file containing the epsts generated for the dataset to provide researchers with a file format they can quickly load into genome browsers for data visualization. example datasets to test our implementation we acquired previously published proteogenomic mapping datasets for a number of organisms. for a relatively small example data set, we selected a proteogenomic mapping dataset for the channel catfish virus. this small dataset contains unique peptide identifications, of which peptides did not map to the predicted proteome of the virus, but do map to novel open reading frames in the viral genome, and expression of several of these genes was confirmed by rt-pcr. our example dataset consists of a fasta file of these peptides and the reference genome for the channel catfish virus. for bacterial examples, proteomics datasets from three different microorganisms were used to test our application. for a eukaryotic example, a previously published proteomics dataset generated from chicken serum was utilized for testing. table details the number of unique peptides and the number of unique peptides mapping uniquely to the genomic database search contained in each of these five datasets.  the output from the proteogenomic mapping pipeline matches the previously published results against our test dataset, and our output provides additional information that not only places the mapped peptides on the appropriate nucleotide strand but also includes the reading frame in which the match occurs. table gives a list of the peptides and corresponding epsts for this dataset. we have also successfully tested this tool for proteogenomic mapping in previously published bacterial and eukaryotic datasets. table provides runtime analysis for each of our five test datasets, and demonstrates that the proteogenomic mapping tool scales well for increasingly large datasets. possible future updates to this application include parallelization of the searches against the genome in all reading frames, and the introduction of better thread support to improve performance further on today's modern increasingly multi-core processors.  the proteogenomic mapping pipeline provides a standalone tool that facilitates a streamlined mapping of peptides to a target genome for structurally genome annotation through the use of proteomics. this software can be used on a variety of current operating systems and is its ability to use a variety of genetic codes makes it easily customizable for researchers performing proteogenomic mapping in a variety of prokaryotes, eukaryotes, and viruses. availability and requirements project name: the proteogenomic mapping pipeline project home page: http://www.agbase.msstate.edu/tools/pgm/ operating system: windows xp, vista, vista, linux, macos programming languages: java other requirements: java license: gnu gplv any restrictions to use by non-academics: none authors' contributions fmm and scb developed the initial procedure for generating epsts. bn and ml developed the algorithms for generating epsts for prokaryotes. smb and nw designed the pipeline and nw implemented the initial perl version of the pipeline. wss and bmm implemented the current java version and the graphical user interface. ysd implemented the string matching module. wss and smb drafted the document. bmm developed the software documentation. all authors read and approved the final manuscript. 
the proteogenomic mapping tool includes a java implementation of the aho-corasick string searching algorithm which takes as input standardized file types and rapidly searches experimentally observed peptides against a given genome translated in all reading frames for exact matches. high-throughput mass spectrometry proteomics data is increasingly being used to complement traditional structural genome annotation methods. allowing the selection of different genetic codes for different organisms allows researchers to easily customize the tool to their own research interests and is recommended for anyone working to structurally annotate genomes using ms derived proteomics data.
 high-throughput mass spectrometry proteomics data is increasingly being used to complement traditional structural genome annotation methods. to keep pace with the high speed of experimental data generation and to aid in structural genome annotation, experimentally observed peptides need to be mapped back to their source genome location quickly and exactly. previously, the tools to do this have been limited to custom scripts designed by individual research groups to analyze their own data, are generally not widely available, and do not scale well with large eukaryotic genomes.  the proteogenomic mapping tool includes a java implementation of the aho-corasick string searching algorithm which takes as input standardized file types and rapidly searches experimentally observed peptides against a given genome translated in all reading frames for exact matches. the java implementation allows the application to scale well with larger eukaryotic genomes while providing cross-platform functionality.  the proteogenomic mapping tool provides a standalone application for mapping peptides back to their source genome on a number of operating system platforms with standard desktop computer hardware and executes very rapidly for a variety of datasets. allowing the selection of different genetic codes for different organisms allows researchers to easily customize the tool to their own research interests and is recommended for anyone working to structurally annotate genomes using ms derived proteomics data. 