An algorithm that solves a linear program by using planes exterior to the feasible region is described. Given a linear program in standard form, a constraint derived from the given objective function is added to the constraint set, and the objective function is removed. The added constraint is designed to make the program initially infeasible. It is then incrementally and unidirectionally moved toward the solution vertex in cycles, which causes the constraint set to change each time. Each cycle consists of two steps: moving the added constraint and testing the updated constraint set for feasibility. Ultimately the moving constraint reaches the solution vertex and the program becomes feasible, this signals both the solution of the program and termination of the algorithm. Because of unidirectionality, the algorithm is guaranteed to terminate. If fixed point arithmetic with B bit numbers is used and feasibility testing complexity with N variables is O(f(N)), then the worst-case complexity of the exterior plane algorithm is 2B O(f(N)). f(N) is O(N3) with the simplex method and ~O(N3.5) with an interior point method. The algorithm can be substantially improved by using binary search, the resulting complexity is B O(f(N)). The algorithm is compared qualitatively with three types of LP algorithms: simplex, ellipsoid, and interior point.

A procedure to identify single amino acids (AAs) in the bulk or with a few molecules from a single binary measurement is introduced. Combined with Edman degradation (or other method) it can be used to sequence a peptide or identify the parent protein from a partial sequence. This binary/digital approach is centered on the superspecificity property of transfer RNAs (tRNAs), it differs markedly from conventional and recent single molecule (SM) sequencing methods based on analog measurements. Each of 20 (or more) terminal residues cleaved from 20 (or more) copies of a peptide enters a different cavity with a unique tRNA; tRNA charging (or binding with AA) occurs only in the cavity with the cognate AA. The bound AA or the AA separated from the tRNA is detected with a single binary measurement; its identity is known from the position of the single high bit in the resulting 20-bit output. Alternatively a 20-stage pipeline can be used with sparse samples. Detection of the bound AA can be done optically by tagging the AAs with a fluorescent dye, of the freed AA electrically with a nanopore. Necessary conditions for accurate AA identification are satisfied in principle; related computations and simulation results are presented. A modified version that can be used for de novo sequencing in parallel of large numbers of peptides immobilized on a glass slide with the tRNAs carrying a fluorescent tag is mooted. Both methods can be used for protein identification from partial sequences containing 2 or 3 AA types by using only the corresponding tRNAs. Potential implementation issues are discussed. With a straightforward extension post-translational modifications (PTMs) in single AAs can be detected. Such detection is horizontal: it is only necessary to search among the PTMs for a given AA, PTMs of the other 19 AAs are not involved.