Weighted isotonic regression under the L1 norm

ABSTRACT

Isotonic regression, the problem of finding values that best fit given observations and conform to specific ordering constraints, has found many applications in biomedical research and other fields. When the constraints form a partial ordering, solving the problem under the L1 error measure takes O(n³) when there are n observations. The analysis of large-scale microarray data, which is one of the important tools in biology, using isotonic regression is hence expensive. This is because in microarray analysis, the same procedure is used for studying the fit of tens of thousands of genes to a given partial order. Fast estimation for the fitting error is therefore highly desired to reduce the number of regression instances through pruning. In this paper, we present approximation algorithms to the isotonic regression problem under the L1 error measure. We relate the problem to an edge packing problem and in the special case when the observations are not weighted, we relate it to a weighted matching problem.

REFERENCES

• 1: Ravindra K. Ahuja , James B. Orlin, A Fast Scaling Algorithm for Minimizing Separable Convex Functions Subject to Chain Constraints, Operations Research, v.49 n.5, p.784-789, September 2001 [doi>10.1287/opre.49.5.784.10601]
• 2: D. Avis, A survey of heuristics for the weighted matching problem, Networks 13 (1983), 475--493.
• 3: M. B. Ayer, H. D. Brunk, G. M. Ewing, W. T. Reid, and E. Silverman, An empirical distribution function for sampling with incomplete information, Annals of Mathematical Statistics 26 (1955), 641--647.
• 4: R. E. Barlow and V. A. Ubhaya, Isotonic approximation, In Optimizing Methods in Statistics (1971), 77--86.
• 5: Amir Ben-Dor, Benny Chor, Richard M. Karp, and Zohar Yakhini, Discovering local structure in gene expression data: The order-preserving submatrix problem, Journal of Computational Biology 10 (2003), no. 3/4, 373--384.
• 6: Victor Boyarshinov and Malik Magdon-Ismail, Linear time isotonic and unimodal regression in the L1 and L∞ norms, Journal of Discrete Algorithms, in press (2005).
• 7: Seiyoung Chung, Dual algorithm for l(1) isotonic optimization on a partially ordered set, 1987
• 8: S. Y. Chung, Dual algorithm forL1isotonic optimization with weights on a partially ordered set, Bulletin of the Korean Mathematical Society 28 (1991), no. 2, 243--254.
• 9: Don Coppersmith , Shmuel Winograd, Matrix multiplication via arithmetic progressions, Journal of Symbolic Computation, v.9 n.3, p.251-280, March 1990 [doi>10.1016/S0747-7171(08)80013-2]
• 10: Thomas H. Cormen , Clifford Stein , Ronald L. Rivest , Charles E. Leiserson, Introduction to Algorithms, McGraw-Hill Higher Education, 2001
• 11: Hirsch I. Dilleen M., Heimann G., Non-parametric estimators of a monotonic dose-response curve and bootstrap confidence intervals, Stat Med. 22 (2003), no. 6, 869--882.
• 12: Doratha E. Drake and Stefan Hougardy, Improved linear time approximation algorithms for weighted matchings, RANDOM-APPROX, 2003, pp. 14--23.
• 13: Jack Edmonds , Richard M. Karp, Theoretical Improvements in Algorithmic Efficiency for Network Flow Problems, Journal of the ACM (JACM), v.19 n.2, p.248-264, April 1972 [doi>10.1145/321694.321699]
• 14: Jason Ernst , Gerard J. Nau , Ziv Bar-Joseph, Clustering short time series gene expression data, Bioinformatics, v.21 n.1, p.159-168, January 2005 [doi>10.1093/bioinformatics/bti1022]
• 15: M. Frisén, Unimodal regression, The Statistician 35 (1980), 304--307.
• 16: Z. Geng and N.-Z. Shi, Isotonic regression for umbrella orderings, Appl. Statist. 39 (1990), 397--424.
• 17: Debashis Ghosh, Moulinath Banerjee, and Pinaki Biswas, Binary isotonic regression procedures, with application to cancer biomarkers, Working Paper, Department of Biostatistics, University of Michigan, 2004.
• 18: A. Ivanova and K. Wang, A non-parametric approach to the design and analysis of two-dimensional dose-finding trials, Stat Med 23 (2004), no. 12, 1861--1870.
• 19: W. S. Jewell, Isotonic optimization in tariff construction, ASTIN Bulletin 8 2 (1975), 175--203.
• 20: K. Leuraud and J. Benichou, A comparison of several methods to test for the existence of a monotonic dose-response relationship in clinical and epidemiological studies, Stat. Med 20 (2001), no. 22, 3335--3351.
• 21: J. Y. Mancuso, H. Ahn H., and J. J. Chen, Order-restricted dose-related trend tests, Stat Med 20 (2001), no. 15, 2305--18.
• 22: William L. Maxwell and John A. Muckstadt, Establishing consistent and realistic reorder intervals in production-distribution systems, Operations Research 33 (1985), no. 6, 1316--1341.
• 23: T. Morton-Jones, P. Diggle, L. Parker, H. O. Dickinson, and K. Binks, Additive isotonic regression models in epidemiology, Stat Med 19 (2000), no. 6, 849--59.
• 24: R. A. Mureika, T. R. Turner, and P. C. Wollan, An algorithm for unimodal isotonic regression, with application to locating a maximum, Univ. New Brunswichk Dept. Math. and Stat. Tech. Report 92--4, 1992.
• 25: P. M. Pardalos, G. L. Xue, and L. Yong, Efficient computation of an isotonic median regression, Appl. Math. Lett 8 (1995), no. 2, 67--70.
• 26: Panos M. Pardalos and Guoliang Xue, Algorithms for a class of isotonic regression problems, Algorithmica 23 (1999), no. 3, 211--222.
• 27: Shyamal D. Peddada, Edward K. Lobenhofer, Leping Li, Cynthia A. Afshari, Clarice R. Weinberg, and David M. Umbach, Gene selection and clustering for time-course and dose-response microarray experiments using order-restricted inference, Bioinformatics 19 (2003), no. 7, 834--841.
• 28: N-G. Pehrsson and M. Frisén, The UREGR procedure, Gothenburg Computer Central, 1983.
• 29: T. Robertson and P. Waltman, On estimating monotone parameters, Ann. Math. Stat. (1968), 1030--1039.
• 30: Quentin Stout, Optimal algorithms for unimodal regression, Computer Science and Statistics, vol. 32, 2000.
• 31: M. Stylianou and N. Flournoy, Dose-finding using the biased coin up-and-down design and isotonic regression, Biometrics 58 (2002), 171--177.
• 32: T. R. Turner, S function unfit to calculate the unimodal isotornic regression of a set of data, Univ. New Brunswichk Dept. Math. and Stat., 1983.
• 33: V. A. Ubhaya, Isotonic optimization I, Approx. Theory 12 (1974), 146--159.
• 34: V. A. Ubhaya, Isotonic optimization II, Approx. Theory 12 (1974), 315--331.
• 35: K. Ulm, Nonparametric analysis of dose-response relationships, Ann. N. Y. Acad. Sci. 895 (1999), 223--231.

INDEX TERMS

Primary Classification:
  J. Computer Applications
  J.3 LIFE AND MEDICAL SCIENCES
      Subjects: Biology and genetics

Additional Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.2 Nonnumerical Algorithms and Problems

  G. Mathematics of Computing
  G.2 DISCRETE MATHEMATICS
      G.2.1 Combinatorics
          Subjects: Combinatorial algorithms

  I. Computing Methodologies
  I.5 PATTERN RECOGNITION
      I.5.2 Design Methodology
          Subjects: Pattern analysis

General Terms:
Algorithms, Design, Theory