Search tips
Search criteria 


Logo of amolbioBioMed CentralBiomed Central Web Sitesearchsubmit a manuscriptregisterthis articleAlgorithms for Molecular Biology : AMB
Algorithms Mol Biol. 2010; 5: 28.
Published online 2010 June 25. doi:  10.1186/1748-7188-5-28
PMCID: PMC2911453

Optimal selection of epitopes for TXP-immunoaffinity mass spectrometry



Mass spectrometry (MS) based protein profiling has become one of the key technologies in biomedical research and biomarker discovery. One bottleneck in MS-based protein analysis is sample preparation and an efficient fractionation step to reduce the complexity of the biological samples, which are too complex to be analyzed directly with MS. Sample preparation strategies that reduce the complexity of tryptic digests by using immunoaffinity based methods have shown to lead to a substantial increase in throughput and sensitivity in the proteomic mass spectrometry approach. The limitation of using such immunoaffinity-based approaches is the availability of the appropriate peptide specific capture antibodies. Recent developments in these approaches, where subsets of peptides with short identical terminal sequences can be enriched using antibodies directed against short terminal epitopes, promise a significant gain in efficiency.


We show that the minimal set of terminal epitopes for the coverage of a target protein list can be found by the formulation as a set cover problem, preceded by a filtering pipeline for the exclusion of peptides and target epitopes with undesirable properties.


For small datasets (a few hundred proteins) it is possible to solve the problem to optimality with moderate computational effort using commercial or free solvers. Larger datasets, like full proteomes require the use of heuristics.


Mass spectrometry (MS) based protein profiling has become one of the key technologies in biomedical research and biomarker discovery. Contrary to the analysis of mRNA profiles, the screening of protein expression profiles allows direct conclusions about the molecular mechanisms involved in a certain condition, because many cellular processes are directly related to the protein functions.

mRNA-Profiling is based on hybridization of DNA-molecules and binding molecules are easy to postulate and to synthesize. This allows the comparatively cheap production of high-density microarrays that cover a large portion of the known genome. Unfortunately this is not applicable in the protein world since features of protein binding molecules can not be predicted as easily.

Mass spectrometry allows a parallel, high-throughput detection of a mixture containing a limited number of peptides [1-3]. For qualitative and quantitative protein profiling of a complex sample time-consuming sample fractionation steps such as 2D gel electrophoresis or multidimensional chromatography are necessary. In this way, small subsets of the sample are analyzed fraction by fraction. The mentioned fractionation methods are the limiting factor in MS-based protein analysis.

Immunoaffinity-MS approaches combine antibody-based approaches with mass-spectrometry, increasing sample throughput and detection sensitivity by capturing proteins or peptides from the sample using protein-or peptide-specific antibodies [4-9]. However, the drawback is the large number of antibodies needed - one antibody per protein. Nevertheless efforts are ongoing to generate antibodies for the analysis of the plasma proteome by an immunoaffinity MS approach [10].

The novel 'Triple X proteomics'-strategy (TXP) [11] uses a special kind of antibodies to immunoprecipitate groups of peptides which share a common short sequence (3-5 amino acids) at the N-or C-terminal end, generated in a tryptic whole proteome digest of a biological sample (see Figure Figure1).1). In contrast to classical peptide antibodies those binders can be selected and generated to bind dozens to hundreds of peptides sharing the same TXP-epitope.

Figure 1
Schematic Immunoaffinity-MS workflow: Sample preparation and digest, fractionation with TXP-antibodies, analysis of the fraction with mass spectrometry.

As the biological proof of concept has been shown, the practical question arose which epitopes should be produced to cover a large set proteins with minimal effort based on prior knowledge of a proteome.

In this work we present a method to select and optimize TXP-antigens, the short common terminal sequences (epitopes), to cover a given set of target proteins. This leads to a substantial reduction of antibodies to be generated for a proteome wide immunoaffinity-MS approach. An in-silico digest of a fully elucidated target proteome is filtered to eliminate those peptides with undesirable properties or epitopes. We show that the problem of selecting the minimal set of TXP-antigens is equivalent to the set cover problem. We apply a greedy algorithm and a boolean programming approach, and extend those methods, to enhance the multiple coverage of the protein targets for a better experimental design.


The goal of the experiment design task is to calculate a minimal set of epitopes to measure a given set of proteins in a complex mixture. The mixture is a digest, that was derived from a tryptic digest of the whole proteome. It is also assumed that the digest is complete (there are no missed or mis-cleavages) and that the proteome of the organism is fully elucidated. Another assumption is that the hypothetical antibody is specific to a given epitope, and does not bind variations or modifications of the epitope.

The process is divided in a filtering pipeline, where the search space is reduced, and the optimization step, where the problem is formulated and then solved.

Filter Pipeline

Starting from a proteome dataset (e.g. Uniprot or IPI) that is defined as the background, an in-silico tryptic digest is obtained. It is assumed that the background dataset holds information about all proteins found in the future sample.

Peptides must have certain properties to be detectable by a read-out method. The mass of the peptide has to be known and, in addition, mass-spectrometers have limits in resolution and mass range. Instead of including these limitations in optimization-constraints, a filter pipeline is applied where peptides and epitopes, which do not match the criteria, are removed.

Here, the digest of a proteome P is defined by a set of pairs D(P) = {(Pi, pj)} where pj is the j-th peptide in protein Pi, pi = a1a2 ... an is an amino acid sequence composed of the single letter amino acid code. We define a peptide-antibody-combination as a quadruple labelled An external file that holds a picture, illustration, etc.
Object name is 1748-7188-5-28-i1.gif:

equation image

Here, l defines the length of the epitope and t describes whether the terminus is n- or c-terminal. The set

equation image


equation image
equation image

contains all combinations for a given proteome, length range and termini. This combination set is the raw start input for the filter pipeline. The quadruple is not needed for every filter, but for reasons of formal continuity we use the definition through the whole specification of the pipeline.

Knowing the weight of captured peptides is essential for the mass spectrometry read-out. Therefore, the 'unknown-positions'-filter removes peptides containing unknown positions (symbol X ), as their weight cannot be calculated.

The methionine filter removes combinations with epitopes containing methionine (symbol M ), since chemical modifications of methionine may hamper the recognition of the target epitope by a binding molecule, especially by an antibody.

The high abundant epitope filter removes combinations with epitopes which would capture a large number of peptides. An antibody affine to such an epitope would be cluttered, and therefore be rather insensitive.

We define a subset Ce [subset or is implied by] C which contains all combinations An external file that holds a picture, illustration, etc.
Object name is 1748-7188-5-28-i6.gif where epitope An external file that holds a picture, illustration, etc.
Object name is 1748-7188-5-28-i7.gif. If |Ce| is bigger than 600, the epitope e would not be considered for optimization.

The weight filter removes combinations which share the same terminus and have almost the same weight.

These peptides can not be measured with standard mass spectrometry read-out, because the resulting peaks would overlap in the spectrum. A reasonable value for Δmin is 2-10 Da for MALDI-TOF-spectrometers. In this filter, rather than excluding the terminus from the optimization only the almost isobaric peptides are not counted as identifiable by combining the specific epitope and mass information. For example the peptides AYEQLGYR and HLEILGYR could not be discriminated in a mass spectrum of a probe enriched with an antibody affine to the epitope LGYR, because the masses only differ by 1.068 Da, if the resolution of the mass spectrometer does not provide the adequate resolution.

The length filter removes combinations which do not fit in the detection range of the mass spectrometer. The detection range depends on the technical specifications of the mass-spectrometer, but a range from 8-30 amino acids is a good rule of thumb.

Some proteins occur with great abundance in the sample, such as actin or tubulin. Terminal epitopes of peptides from these proteins are unsuitable as epitopes for immunoaffinity experiments for the same reasons explained in the high abundant epitope filter. In this last filter step an epitope stop list, generated from a hand cured list of high-abundant proteins, is used to remove those from list of combinations. As shown in figure figure22 filters are usually applied in a specific order. While the methionine, unknown positions, high abundant protein filters can be applied at any position in the pipeline, other filters are order-dependent. This is the case if a filter evaluates the expected peptide distribution Ce of an epitope e. These filters cannot be preceded by filters that change those distributions. The high abundant epitope filter must precede the weight filter, which must precede the length filter.

Figure 2
Filter pipeline.

Through the application of this filter pipeline the preselection of epitopes is adjusted to the experimental setup and the problem dimension is significantly reduced.

The influence of the filters is shown in Table Table1.1. While the unknown-positions-filter and the methionine-filter have a relatively small impact, the high abundant epitope filter and the weight filter remove a large number of combinations. The weight filters reduce the number of combinations by about 43%, while the number of epitopes is only reduced by 3%. The filter removes combinations from the set, which cannot contribute to the coverage (overlapping peaks). Still the corresponding antibody can capture peptides that are detectable by the mass spectrometer.

Table 1
Filter impact

Some antibodies ('robinson antibodies') capture only one peptide from one protein. If there is an antibody that captures more peptides from the same protein and others, it is always better to choose this one over the 'robinson antibody'. Therefore all robinson antibodies are removed from the graph before the optimization starts.

Protein set cover problem formulation

The bipartite graph G = (P [union or logical sum] A, E) is constructed by adding proteins and epitopes as vertices, and by connecting a protein node from the protein set P and an epitope node from the epitope set A if a combination appears in the filtered set:

equation image
equation image

The problem is to select a minimal set of antibodies Amin [subset or is implied by] A so that every protein in P is covered by at least one epitope. The minimum set cover is a classical problem in computer science and complexity theory.

The set cover can be formulated as a decision problem, where the question is asked, if a covering set of size k or less exists. This problem was shown to be NP-complete and achieving approximation ratios is no easier than computing optimal solutions. [12] The optimization version where the smallest covering set has to be found is NP-hard. It was shown that a greedy algorithm (see appendix) has an approximation ratio of

equation image

where n is the size of the largest set. [13]

This the best approximation ratio for the set cover problem [14]. In this algorithm in each step the epitope in A covering the most yet uncovered proteins in P, is added to the solution set L, until all proteins are covered.

Another approach to the solution of the set cover problem is to formulate it as a binary linear program. The binary decision variables sa reflect the inclusion of an epitope a to the solution set. The number of the selected epitopes forms the objective function:

equation image
equation image
equation image

The linear program is subject to the constraint that every protein P has to be covered by one or more epitopes in the solution:

equation image
equation image

This program can be solved with available solvers such as CPLEX or GLPK. This will lead to optimal solutions, if the problem dimension is small.

To enhance the accuracy of the proteomics experiments, it would be beneficial to capture the same or multiple peptides from a protein by different binders. In addition it is beneficial to include alternative binders in the experimental planning, in case the generation of a binder affine to a specific epitope fails. The multicovering problem (MCP) is a generalization of the set covering problem. Several algorithms have been proposed by Dobson [15], Hochbaum, Hall [16] and Rajagopalan [17]. Those heuristics would solve the problem of covering each protein twice or more. As it would be cost-prohibitive to double the number of binders, it is not possible to cover all target proteins more than once. This is the case at least for proteins that are covered by a very specific epitope. The following approach solves the pragmatic variant of the problem.

The greedy algorithm can be modified to enhance the probability of the selection of an epitope set that meets the multicoverage requirement for the target proteins.

In this variant (see appendix) the scoring function combines two different optimization targets, minimality and redundancy, by summation to a one-dimensional multiobjective fitness function.

The function is a weighted sum of the number of proteins which are not yet covered

equation image

and the number of proteins which are covered again by this antibody

equation image

E denotes the edge set in the bipartite graph and Pcov the set of already covered proteins. The influence of new and already covered proteins on the overall score of an epitope is weighted by the parameters smcov and scov:

equation image

Still the algorithm terminates with a total number of epitopes lower or equal as the number targets, because every added epitope is required to cover at least one new target protein.

The choice of the parameters smcov and scov has a high impact on the results, and depends heavily on the size of the dataset. The number of epitopes with high capacity is considerably lower in small datasets than in large datasets. Because of this the probability that a protein can be covered more than once by different high capacity epitopes is small. In large datasets the situation is the opposite. As many epitopes have a very large capacity, and possibly cover up to a few hundred peptides from many different proteins, it is more probable that the sets of captured proteins overlap. In this configuration it is better to score innovation over redundancy. While this is intuitively clear, it would be a big effort to determine the best values analytically. For large datasets should smcov should be chosen smaller than scov, for small datasets smcov >scov.

Multiple coverage can be integrated to the Integer Program formulation by changing the coverage constraints to

equation image

for all proteins that can be covered twice. However this will lead to inclusion of elongated, already selected, epitopes (e.g. IER and EIER), to satisfy the double coverage constraints.

This formulation requires that all proteins are multiply covered by the solution. A better formulation reads as follows: Maximize the number of multiply covered proteins in a valid covering of all proteins, by using a fixed number of epitopes. The objective function maximizes the number of proteins which are multi-covered.

equation image

If the binary variable Si is set to one, protein i has to be covered at least twice. This is guaranteed by using the following constraint:

equation image

If Si is selected, at least two covering epitopes have to be selected in order to satisfy the constraint. This problem would be easily solved just by picking two epitopes randomly for each protein. In order the get an optimal usage of the epitopes their number is restricted by an additional constraint:

equation image

Here costmax denotes the maximum number of antibodies to be chosen, and this has to be set by the user and may just depend on the available funding for antibody generation or purchase. An upper bound for costmax is the size of the optimal solution to the original multicover ILP, which already covers all proteins in the dataset twice or more. A lower bound is the minimal cost for the normal covering.

Results and Discussion

Proteomes of various organisms (Homo sapiens, Mus musculus, Rattus norvergicus, Bos taurus, Saccharomyces cervisiae) were obtained from UniProtKB [18]. Only reviewed sequences were included in the dataset. The proteomes were trypsin-digested in-silico, by cutting after lysine (K) or arginine (R), if no proline (P) followed. A complete digest without missed cleavages or mis-cleavages was assumed. The resulting digests were pre-processed and filtered as described. To investigate the use case of assay designs for a limited number of targets, the lists of proteins associated to the pathways for TGFß , WNT and TLR signaling were obtained from the KEGG (Kyoto Encyclopedia of Genes and Genomes) PATHWAY database [19]. The KEGG gene IDs in the pathway descriptions were mapped to Uniprot IDs. The combination sets for the pathways were extracted from the filtered combination set of the human proteome. The coverage score An external file that holds a picture, illustration, etc.
Object name is 1748-7188-5-28-i24.gif of a solution L is the number of required epitopes relative to the number of proteins to cover.

The solutions of the integer program delivered by the industry standard ILP solver CPLEX after a limited running time of 12 hours were, not surprisingly, superior to the solutions provided by the greedy algorithm on all tested proteomes and epitope-length combinations (see Table Table2).2). The inclusion of epitopes of length five increased the problem dimension considerably, because of the much larger number of potential epitope sequences (An external file that holds a picture, illustration, etc.
Object name is 1748-7188-5-28-i25.gif). This increased the number of coverable proteins in the final combination set.

Table 2
Solutions for proteome datasets

Nevertheless the number of required epitopes was decreased in three of five proteomes (Homo sapiens, Rattus norvegicus, Bos taurus). When including terminal sequences of length four and five, the set cover will include shorter epitopes in most cases as they cover more proteins. If for a specific protein all epitopes of length four have been filtered out, longer sequences can still be used to cover it.

The solutions provided by the multicoverage integer program are significantly larger than the solutions, in which multicoverage was not enforced. The multicoverage greedy approach only favors but does not enforce multicoverage, so the solutions provided by this method are smaller, but not necessarily superior to those provided by the multicoverage integer program. As shown in Table Table33 the number of multicovered proteins (Homo sapiens, length = 4) was increased from 14,847 (Greedy) to 15,853 (Greedy MC) by only eight additional epitopes in the solution, compared to the solution of the standard greedy algorithm. This was achieved with a setting of scov = 100; smcov = 1, which scores not yet covered proteins one hundred times higher than already covered proteins. The solution of the IP MC is 3.895 large, so the effort of multicovering all 19,756 proteins nearly doubles the number of epitopes compared to the solution of the standard IP, where only 13,815 proteins are multicovered. By using IP MMC with the costmax set to the solution size of the Greedy MC the number of multicovered proteins was increased from 15,853 to 16,314.

Table 3
multicoverage of the human proteome

On the smaller pathway datasets it is possible to calculate the best possible solutions with CPLEX and GLPK in a very short amount of time (less than 2 seconds). Table Table44 shows a comparison of the solution size and the multicoverage percentages on pathway datasets. On pathway datasets the solution sets are proportionally larger than on proteome datasets. This was expected, because the probability of shared terminal epitopes is smaller if the number of target proteins is reduced. Nevertheless coverage scores of 42% (WNT, length = 4-5, IP, 55 epitopes to cover 133 proteins) are a substantial improvement to the scenario of choosing peptide-or protein-specific antibodies for immunoaffinity-MS. The multicoverage integer program provided solutions with coverage scores from 81% (WNT, length = 4-5) to 100% (TLR, length = 4).

Table 4
Pathway results

The settings of the multicoverage greedy algorithm were changed to scov = 1 and smcov = 10, because the probability of multicoverage through one epitope is proportional to the size of the datasets. In this way the multicoverage score begins to take effect earlier during the iterative optimization. Table Table55 contains results of a grid search on the parameters of the greedy MC algorithm applied to the WNT pathway example. The multicoverage enhancing effect shows only if already covered proteins are scored higher than new proteins.

Table 5
Grid search on the parameters scov and smcov

If scov is chosen bigger than smcov the multicoverage effect almost completely vanishes on small datasets. After the calculation of the greedy multicover the resulting cost (solution size) was used as the cost limit costmax for the maximization multicover (IP MMC) formulation. The results were significantly better multicoverage percentages for all datasets for the same costs (Table (Table4,4, compare columns Greedy MC and IP MMC).

Results, coverage reports and the used software package SCPSolver are available on the website


Starting from the real-world lab engineering task, we have shown that the problem of choosing a minimal set of epitopes is equivalent to the well-known set cover problem. In combination with a filter pipeline that eliminates unsuitable peptide-epitope combinations, we proposed different methods for the solution of the problem.

For small datasets (a few hundred proteins) it is possible to solve the problem to optimality with minimal computational effort using commercial or free solvers. Larger datasets, like full proteomes, require the use of heuristics, or respectively a running time limitation of the branch-and-bound search in the integer program solvers. Large sets of proteins can theoretically be covered by TXP-antibodies with a fraction (down to 9.57%, see Table Table3)3) of the otherwise required peptide-specific antibodies for every protein. We further proposed methods to enforce (IP MC) or enhance (Greedy MC, IP MMC) the multiple coverage of a protein for a better experimental design.

The results presented in this paper were used to generate concrete lists of candidate epitopes, which are currently in production and evaluation in the NMI lab. While it is not yet clear whereif the TXP approach scales up to the proteome level, first results are promising.

In future work scheduling of binder generation, to get a broad coverage effect of interesting targets early, and other experimental setups, e.g. sandwich immunoassays based on TXP-antibodies, will lead to new interesting design optimization tasks on a higher level of complexity.

Competing interests

TJ, OP, DS and MT are co-authors of the patent application WO2007/112927/A1 which describes the Triple X Proteomics approach. HP, JS, TJ, OP, DS, MT and AZ are co-authors of an International Patent Application PCT/EP2009/0001230 that will be published in August 2010 and is related to the epitope selection approach for TXP described in this paper.

Authors' contributions

HP wrote the paper. JS implemented large parts of the filter pipeline. HP implemented the optimization routines and SCPSolver. OP, DS, MT an TJ provided the biological and biochemical input, including the problem. AZ supervised the work and corrected the paper. All authors read and approved the final manuscript.


Input: bipartite epitope-protein graph G(P [union or logical sum] A, E)

Output: set of epitopes L

Pcov = [empty];

L = [empty];

while P\Pcov = [empty]; do

   foreach a [set membership] A\L do

      //calculate how many new proteins are covered by the epitope a score

      score(a) = |{(a, p) [set membership] E|p [negated set membership] Pcov}|;


   //select the epitope a with the highest score

   as = arg maxa score(a);

   L = L [union or logical sum] {as};

   Pcov = Pcov [union or logical sum] {p|(as, p) [set membership] E};

   //remove the covered proteins from the graph

   G = G((A [union or logical sum] P)\(Pcov [union or logical sum] L), E\{(as, P) [set membership] E});


return L

                  Algorithm 1: The greedy set cover algorithm

Input: bipartite epitope-protein graph G(P [union or logical sum] A, E), scov, smcov

Output: set of epitopes L

Pcov = [empty];

L = [empty];

while P\Pcov [empty]; do

   foreach a [set membership] A\L do

      //here the score favorizes the multiple coverage of proteins

      An external file that holds a picture, illustration, etc.
Object name is 1748-7188-5-28-i27.gif


   as = arg maxa score(a);

   L = L [union or logical sum] {as};

   Pcov = Pcov [union or logical sum] {p|(as, p) [set membership] E};

   E = {(a, p) [set membership] E|[exists](a, An external file that holds a picture, illustration, etc.
Object name is 1748-7188-5-28-i28.gif [negated set membership] Pcov) [set membership] E}):


return L

         Algorithm 2: The multicoverage greedy set cover algorithm (Greedy MC)


This work was funded by Wellspring Clinical Lab, Inc. (Altamonte Springs, FL, USA) and the NMI

Naturwissenschaftliches und Medizinisches Institut an der Universität Tübingen (Reutlingen, Germany).


  • Aebersold R, Mann M. Mass spectrometry-based proteomics. Nature. 2003;422(6928):198–207. doi: 10.1038/nature01511. [PubMed] [Cross Ref]
  • Washburn M, Wolters D, Yates. Large-scale analysis of the yeast proteome by multidimensional protein identification technology. Nat Biotechnol. 2001;19(3):242–247. doi: 10.1038/85686. [PubMed] [Cross Ref]
  • Gygi S, Corthals G, Zhang Y, Rochon Y, Aebersold R. Evaluation of two-dimensional gel electrophoresis-based proteome analysis technology. Proc Natl Acad Sci USA. 2000;97(17):9390–9395. doi: 10.1073/pnas.160270797. [PubMed] [Cross Ref]
  • Warren E, Elms P, Parker C, Borchers C. Development of a protein chip: a MS-based method for quantitation of protein expression and modification levels using an immunoaffinity approach. Anal Chem. 2004;76(14):4082–4092. doi: 10.1021/ac049880g. [PubMed] [Cross Ref]
  • Anderson N, Anderson N, Haines L, Hardie D, Olafson R, Pearson T. Mass spectrometric quantitation of peptides and proteins using Stable Isotope Standards and Capture by Anti-Peptide Antibodies (SISCAPA) J Proteome Res. 2004;3(2):235–244. doi: 10.1021/pr034086h. [PubMed] [Cross Ref]
  • Keshishian H, Addona T, Burgess M, Kuhn E, Carr S. Quantitative, multiplexed assays for low abundance proteins in plasma by targeted mass spectrometry and stable isotope dilution. Mol Cell Proteomics. 2007;6(12):2212–2229. doi: 10.1074/mcp.M700354-MCP200. [PMC free article] [PubMed] [Cross Ref]
  • Whiteaker J, Zhao L, Anderson L, Paulovich A. An automated and multiplexed method for high throughput peptide immunoaffinity enrichment and multiple reaction monitoring mass spectrometry-based quantification of protein biomarkers. Mol Cell Proteomics. 2010;9:184–196. doi: 10.1074/mcp.M900254-MCP200. [PMC free article] [PubMed] [Cross Ref]
  • Anderson N, Jackson A, Smith D, Hardie D, Borchers C, Pearson T. SISCAPA peptide enrichment on magnetic beads using an inline beadtrap device. Mol Cell Proteomics. 2009. [PMC free article] [PubMed]
  • Nicol G, Han M, Kim J, Birse C, Brand E, Nguyen A, Mesri M, FitzHugh W, Kaminker P, Moore P, Ruben S, He T. Use of an immunoaffinity-mass spectrometry-based approach for the quantification of protein biomarkers from serum samples of lung cancer patients. Mol Cell Proteomics. 2008;7(10):1974–1982. doi: 10.1074/mcp.M700476-MCP200. [PubMed] [Cross Ref]
  • Anderson N, Anderson N, Pearson T, Borchers C, Paulovich A, Patterson S, Gillette M, Aebersold R, Carr S. A human proteome detection and quantitation project. Mol Cell Proteomics. 2009;8(5):883–886. doi: 10.1074/mcp.R800015-MCP200. [PMC free article] [PubMed] [Cross Ref]
  • Poetz O, Hoeppe S, Templin M, Stoll D, Joos T. Proteome wide screening using peptide affinity capture. Proteomics. 2009;9(6):1518–1523. doi: 10.1002/pmic.200800842. [PubMed] [Cross Ref]
  • The approximability of NP-hard problems. ACM New York, NY, USA; 1998.
  • Lund C, Yannakakis M. On the hardness of approximating minimization problems. J ACM. 1994;41(5):960–981. doi: 10.1145/185675.306789. [Cross Ref]
  • Feige U. A threshold of ln n for approximating set cover. Journal of the ACM (JACM) 1998;45(4):634–652. doi: 10.1145/285055.285059. [Cross Ref]
  • Dobson G. Worst-Case Analysis of Greedy Heuristics for Integer Programming with Nonnegative Data. Mathematics of Operations Research. 1982;7(4):515–531. doi: 10.1287/moor.7.4.515. [Cross Ref]
  • Nicholas DSH, Hall G. The multicovering problem. European Journal of Operational Research. 1992;62:323–339. doi: 10.1016/0377-2217(92)90122-P. [Cross Ref]
  • Rajagopalan V S. Primal-dual RNC approximation algorithms for (multi)-set (multi)-cover and covering integer programs. Foundations of Computer Science, Annual IEEE Symposium on. 1993;0:322–331.
  • Wu C, Apweiler R, Bairoch A, Natale D, Barker W, Boeckmann B, Ferro S, Gasteiger E, Huang H, Lopez R, Magrane M, Martin M, Mazumder R, O'Donovan C, Redaschi N, Suzek B. The Universal Protein Resource (UniProt): an expanding universe of protein information. Nucleic Acids Res. 2006. pp. D187–91. [PMC free article] [PubMed] [Cross Ref]
  • Ogata H, Goto S, Sato K, Fujibuchi W, Bono H, Kanehisa M. KEGG: Kyoto Encyclopedia of Genes and Genomes. Nucleic Acids Res. 1999;27:29–34. doi: 10.1093/nar/27.1.29. [PMC free article] [PubMed] [Cross Ref]

Articles from Algorithms for Molecular Biology : AMB are provided here courtesy of BioMed Central