Ehrhart polynomials, successive minima, and an Ehrhart theory for rational dilates of a rational polytope

Magdeburg, Univ., Fak. für Mathematik, Diss., 2011

Approximate polytope ensemble for one-class classification

In this work, a new one-class classification ensemble strategy called approximate polytope ensemble is presented. The main contribution of the paper is threefold. First, the geometrical concept of convex hull is used to define the boundary of the target class defining the problem. Expansions and contractions of this geometrical structure are introduced in order to avoid over-fitting. Second, the decision whether a point belongs to the convex hull model in high dimensional spaces is approximated by means of random projections and an ensemble decision process. Finally, a tiling strategy is proposed in order to model non-convex structures. Experimental results show that the proposed strategy is significantly better than state of the art one-class classification methods on over 200 datasets.

Twistor and polytope interpretations for subleading color one-loop amplitudes

Conselho Nacional de Desenvolvimento Científico e Tecnológico (CNPq)

A polytope DNA vaccine elicits multiple effector and memory CTL responses and protects against human papillomavirus 16 E7-expressing tumour

Vaccine-induced CD8 T cells directed to tumourspecific antigens are recognised as important components of protective and therapeutic immunity against tumours. Where tumour antigens have pathogenic potential or where immunogenic epitopes are lost from tumours, development of subunit vaccines consisting of multiple individual epitopes is an attractive alternative to immunising with whole tumour antigen. In the present study we investigate the efficacy of two DNA-based multiepitope('polytope') vaccines containing murine (H-2(b)) and human (HLA-A* 0201)-restricted epitopes of the E7 oncoprotein of human papillomavirus type 16, in eliciting tumour-protective cytotoxic T-lymphocyte (CTL) responses. We show that the first of these polytopes elicited powerful effector CTL responses ( measured by IFN-gamma ELISpot) and long-lived memory CTL responses ( measured by functional CTL assay and tetramers) in immunised mice. The responses could be boosted by immunisation with a recombinant vaccinia virus expressing the polytope. Responses induced by immunisation with polytope DNA alone partially protected against infection with recombinant vaccinia virus expressing the polytope. Complete protection was afforded against challenge with an E7-expressing tumour, and reduced growth of nascent tumours was observed. A second polytope differing in the exact composition and order of CTL epitopes, and lacking an inserted endoplasmic reticulum targeting sequence and T-helper epitope, induced much poorer CTL responses and failed to protect against tumour challenge. These observations indicate the validity of a DNA polytope vaccine approach to human papillomavirus E7 - associated carcinoma, and underscore the importance of design in polytope vaccine construction.

Delivery of multiple CD8 cytotoxic T cell epitopes by DNA vaccination

Development of CD8 alpha beta CTL epitope-based vaccines requires an effective strategy capable of co-delivering large numbers of CTL epitopes, Here we describe a DNA plasmid encoding a polyepitope or polytope protein, which contained multiple contiguous minimal murine CTL epitopes, Mice vaccinated with this plasmid made MHC-restricted CTL responses to each of the epitopes, and protective CTL were demonstrated in recombinant vaccinia virus, influenza virus, and tumor challenge models, CTL responses generated by polytope DNA plasmid vaccination lasted for 1 yr, could be enhanced by co-delivering a gene for granulocyte-macrophage CSF, and appeared to be induced in the absence of CD4 T cell-mediated help, The ability to deliver large numbers of CTL epitopes using relatively small polytope constructs and DNA vaccination technology should find application in the design of human epitope-based CTL vaccines, in particular in vaccines against EBV, HIV, and certain cancers.

Papillomavirus virus-like particles for the delivery of multiple cytotoxic T cell epitopes

Chimeric papillomavirus (PV) virus-like particles (VLPs) based on the bovine papillomavirus type 1 (BPV-1) L1 protein were constructed by replacing the 23-carboxyl-terminal amino acids of the BPV1 major protein L1 with an artificial polytope minigene, containing known CTL epitopes of human PV16 E7 protein, HIV IIIB gp120 P18, Nef, and reverse transcriptase (RT) proteins, and an HPV16 E7 linear B epitope. The CTL epitopes were restricted by three different MHC class 1 alleles (H-2(b), H-2(d), HLA-A*0201). The chimeric L1 protein assembled into VLPs when expressed in SF-9 cells by recombinant baculovirus. After immunization of mice with polytope VLPs in the absence of adjuvant, serum antibodies were detected which reacted with both polytope VLPs and wild-type BPV1L1 VLPs, in addition to the HPV16E7 linear B cell epitope. CTL precursors specific for the HPV16 E7, HIV P18, and RT CTL epitopes were also detected in the spleen of immunized mice. Polytope VLPs can thus deliver multiple B and T epitopes as immunogens to the MHC class I and class II pathways, extending the utility of VLPs as self-adjuvanting immunogen delivery systems. (C) 2000 Academic Press.

Development and characterisation of recombinant hepatitis delta virus-like particles

Injection of particulate hepatitis B virus surface antigen (HBsAg) in mice leads to the induction of a HBsAg-specific class-I-restricted cytotoxic T lymphocyte (CTL) response. It is proposed that any protein internal to HBsAg will also be able to elicit a specific CTL response. In this study, several carboxy-terminal truncations of hepatitis C virus (HCV) core protein were fused to varying lengths of amino-terminal truncated large hepatitis delta antigen (L-HDAg). These constructs were analysed for their ability to be expressed and the particles secreted in the presence of HBsAg after transfection into HuH-7 cells. The secretion efficiency of the various HCV core-HDAg chimeric proteins was generally poor. Constructs containing full length HDAg appeared to be more stable than truncated versions and the length of the inserted protein was restricted to around 40 amino acids. Thus, the use of L-HDAg as a chimera to package foreign proteins is limited. Consequently, a polyepitope (polytope) containing a B-cell epitope from human papillomavirus (HPV 16) and multiple T-cell epitopes from the HCV polyprotein was used to create the construct, L-HDAg-polyB. This chimeric protein was shown to be reliant on the co-expression of HBsAg for secretion into the cell culture fluid and was secreted more efficiently than the previous HCV core-HDAg constructs. These L-HDAg-polyB virus-like particles (VLPs) had a buoyant density of similar to 1.2 g/cm(3) in caesium chloride and similar to 1.15 g/cm(3) in sucrose. The VLPs were also immunoprecipitated using an anti-HBs but not an anti-HD antibody. Thus, these recombinant VLPs have similar biophysical properties to L-HDAg VLPs.

Cytotoxic T cell polyepitope vaccines delivered by ISCOMs

CD8 alpha beta cytotoxic T lymphocyte (CTL) polyepitope or polytope vaccines have traditionally been delivered using recombinant vector or DNA based delivery modalities. Here we show the delivery of polytope vaccines in the form of either synthetic polypeptides or recombinant polytope proteins by ImmunoStimulatory COMplexes (ISCOMs (R)). Induction of multiple protective CTL responses by these polytope-ISCOM formulations were comparable to viral vector or DNA based delivery modalities as assessed by IFN gamma ELISpot, chromium release and viral challenge assays. Measurement of CTL responses specific for the different epitopes revealed imunodominance patterns, which were largely independent of the vaccine vector or the order of the epitopes in the polytope. ISCOMs thus emerge as a viable human delivery modality for protein-based polytope vaccines. (C) 2001 Elsevier Science Ltd. All rights reserved.

Limitations of HLA-transgenic mice in presentation of HLA-restricted cytotoxic T-cell epitopes from endogenously processed human papillomavirus type 16 E7 protein

We investigated the use of mice transgenic for human leucocyte antigen (HLA) A*0201 antigen-binding domains to test vaccines composed of defined HLA A*0201-restricted cytotoxic T-lymphocyte (CTL) epitopes of human papillomavirus (HPV) type 16 E7 oncoprotein. HPV is detected in >90% of cervical carcinomas. HPV16 E7 oncoprotein transforms cells of the uterine cervix and functions as a tumour-associated antigen to which immunotherapeutic strategies may be directed. We report that although the HLA A*0201 E7 epitope peptides function both to prime for E7 CTL responses, and to sensitize target cells for E7-directed CTL killing in situations where antigen processing is not required, the epitopes are not processed out of either endogenously expressed or immunization-introduced E7, by the mouse antigen-processing and presentation machinery. Thus (1) CTL induced by HLA A*0201 peptide immunization killed E7 peptide-pulsed target cells, but did not kill target cells expressing whole E7; (2) immunization with whole E7 protein did not elicit CTL directed to HLA A*0201-restricted E7 CTL epitopes; (3) HLA A*0201-restricted CTL epitopes expressed in the context of a DNA polytope vaccine did not activate E7-specific T cells either in 'conventional' HLA A*0201 transgenic (A2.1K(b) ) mice, or in HHD transgenic mice in which expression of endogenous H-2 class 1 is precluded; and (4) HLA A*0201 E7 peptide epitope immunization was incapable of preventing the growth of an HLA A*0201- and E7-expressing tumour. There are generic implications for the universal applicability of HLA-class 1 transgenic mice for studies of human CTL epitope presentation in murine models of human infectious disease where recognition of endogenously processed antigen is necessary. There are also specific implications for the use of HLA A2 transgenic mice for the development of E7-based therapeutic vaccines for cervical cancer.

Generation of CTL responses using Kunjin replicon RNA

The Kunjin replicon was used to express a polytope that consisted of seven hepatitis C virus cytotoxic T lymphocyte epitopes and one influenza cytotoxic T lymphocyte epitope for vaccination studies. The self-replicating nature of, and expression from, the ribonucleic acid was confirmed in vitro . Initial vaccinations with one dose of Kun-Poly ribonucleic acid showed that an influenza-specific cytotoxic T lymphocyte response was elicited more efficiently by intradermal inoculation compared with intramuscular delivery. Two micrograms of ribonucleic acid delivered in the ear pinnae of mice was sufficient to elicit a detectable cytotoxic T lymphocyte response 10 days post-vaccination. Further vaccination studies showed that four of the seven hepatitis C virus cytotoxic T lymphocyte epitopes were able to elicit weak cytotoxic T lymphocyte responses whereas the influenza epitope was able to elicit strong, specific cytotoxic T lymphocyte responses following three doses of Kun-Poly ribonucleic acid. These studies vindicate the use of the Kunjin replicon as a vector to deliver encoded proteins for the development of cell-mediated immune responses.

On Certain Greedoid Polyhedra, Partially Indexable Scheduling Problems, and Extended Restless Bandit Allocation Indices

We present a polyhedral framework for establishing general structural properties on optimal solutions of stochastic scheduling problems, where multiple job classes vie for service resources: the existence of an optimal priority policy in a given family, characterized by a greedoid (whose feasible class subsets may receive higher priority), where optimal priorities are determined by class-ranking indices, under restricted linear performance objectives (partial indexability). This framework extends that of Bertsimas and Niño-Mora (1996), which explained the optimality of priority-index policies under all linear objectives (general indexability). We show that, if performance measures satisfy partial conservation laws (with respect to the greedoid), which extend previous generalized conservation laws, then the problem admits a strong LP relaxation over a so-called extended greedoid polytope, which has strong structural and algorithmic properties. We present an adaptive-greedy algorithm (which extends Klimov's) taking as input the linear objective coefficients, which (1) determines whether the optimal LP solution is achievable by a policy in the given family; and (2) if so, computes a set of class-ranking indices that characterize optimal priority policies in the family. In the special case of project scheduling, we show that, under additional conditions, the optimal indices can be computed separately for each project (index decomposition). We further apply the framework to the important restless bandit model (two-action Markov decision chains), obtaining new index policies, that extend Whittle's (1988), and simple sufficient conditions for their validity. These results highlight the power of polyhedral methods (the so-called achievable region approach) in dynamic and stochastic optimization.

Beyond Smith's rule: An optimal dynamic index, rule for single machine stochastic scheduling with convex holding costs

Most research on single machine scheduling has assumedthe linearity of job holding costs, which is arguablynot appropriate in some applications. This motivates ourstudy of a model for scheduling $n$ classes of stochasticjobs on a single machine, with the objective of minimizingthe total expected holding cost (discounted or undiscounted). We allow general holding cost rates that are separable,nondecreasing and convex on the number of jobs in eachclass. We formulate the problem as a linear program overa certain greedoid polytope, and establish that it issolved optimally by a dynamic (priority) index rule,whichextends the classical Smith's rule (1956) for the linearcase. Unlike Smith's indices, defined for each class, ournew indices are defined for each extended class, consistingof a class and a number of jobs in that class, and yieldan optimal dynamic index rule: work at each time on a jobwhose current extended class has larger index. We furthershow that the indices possess a decomposition property,as they are computed separately for each class, andinterpret them in economic terms as marginal expected cost rate reductions per unit of expected processing time.We establish the results by deploying a methodology recentlyintroduced by us [J. Niño-Mora (1999). "Restless bandits,partial conservation laws, and indexability. "Forthcomingin Advances in Applied Probability Vol. 33 No. 1, 2001],based on the satisfaction by performance measures of partialconservation laws (PCL) (which extend the generalizedconservation laws of Bertsimas and Niño-Mora (1996)):PCL provide a polyhedral framework for establishing theoptimality of index policies with special structure inscheduling problems under admissible objectives, which weapply to the model of concern.

On certain greedoid polyhedra, partially indexable scheduling problems and extended restless bandit allocation indices

We present a polyhedral framework for establishing general structural properties on optimal solutions of stochastic scheduling problems, where multiple job classes vie for service resources: the existence of an optimal priority policy in a given family, characterized by a greedoid(whose feasible class subsets may receive higher priority), where optimal priorities are determined by class-ranking indices, under restricted linear performance objectives (partial indexability). This framework extends that of Bertsimas and Niño-Mora (1996), which explained the optimality of priority-index policies under all linear objectives (general indexability). We show that, if performance measures satisfy partial conservation laws (with respect to the greedoid), which extend previous generalized conservation laws, then theproblem admits a strong LP relaxation over a so-called extended greedoid polytope, which has strong structural and algorithmic properties. We present an adaptive-greedy algorithm (which extends Klimov's) taking as input the linear objective coefficients, which (1) determines whether the optimal LP solution is achievable by a policy in the given family; and (2) if so, computes a set of class-ranking indices that characterize optimal priority policies in the family. In the special case of project scheduling, we show that, under additional conditions, the optimal indices can be computed separately for each project (index decomposition). We further apply the framework to the important restless bandit model (two-action Markov decision chains), obtaining new index policies, that extend Whittle's (1988), and simple sufficient conditions for their validity. These results highlight the power of polyhedral methods (the so-called achievable region approach) in dynamic and stochastic optimization.

Computing the diameter of Coxeter groups

This thesis addresses the problem of computing the minimal and maximal diameter of the Cayley graph of Coxeter groups. We first present and assert relevant parts of polytope theory and related Coxeter theory. After this, a method of contracting the orthogonal projections of a polytope from Rd onto R2 and R3, d ¸ 3 is presented. This method is the Equality Set Projection algorithm that requires a constant number of linearprogramming problems per facet of the projection in the absence of degeneracy. The ESP algorithm allows us to compute also projected geometric diameters of high-dimensional polytopes. A representation set of projected polytopes is presented to illustrate the methods adopted in this thesis.

Estimation bayésienne nonparamétrique de copules

Thèse numérisée par la Division de la gestion de documents et des archives de l'Université de Montréal