Finding optimal parameters for edit distance based sequence classification is NP-hard

ABSTRACT

Parametric edit distance based classification has been applied to two significant problems in the bioinformatics area: biological sequence analysis (DNA, RNA, protein), and semantic relationship extraction from biomedical scientific literature. This method is based on the edit distance measure on sequences, with parametric costs for matching, mismatching, inserts, and deletes of letters. We present a proof that finding optimal parameter values for such classification based on training data is an NP-hard problem, which is an important claim to justify the use of heuristic methods for determining the best parameter values.

REFERENCES

• 1: Sophia Ananiadou , John Mcnaught, Text Mining for Biology And Biomedicine, Artech House, Inc., Norwood, MA, 2005
• 2: BioCreative challenge. Accessed in August 2008, http://biocreative.sourceforge.net/.
• 3: Thomas H. Cormen , Charles E. Leiserson , Ronald L. Rivest , Clifford Stein, Introduction to Algorithms, Third Edition, The MIT Press, 2009
• 4: J. Hakenberg, C. Plake, U. Leser, H. Kirsch, and D. Rebholz-Schuhmann. Lll'05 challenge: Genic interaction extraction with alignments and finite state automata. In Proceedings of Learning Language in Logic Workshop (LLL'05) at ICML, page 38ÍC45, Bonn, Germany, 2005.
• 5: Jiawei Han , Micheline Kamber, Data mining: concepts and techniques, Morgan Kaufmann Publishers Inc., San Francisco, CA, 2000
• 6: Minlie Huang , Xiaoyan Zhu , Yu Hao , Donald G. Payan , Kunbin Qu , Ming Li, Discovering patterns to extract protein--protein interactions from full texts, Bioinformatics, v.20 n.18, p.3604-3612, December 2004 [doi>10.1093/bioinformatics/bth451]
• 7: Hyunchul Jang , Jaesoo Lim , Joon-Ho Lim , Soo-Jun Park , Kyu-Chul Lee , Seon-Hee Park, Finding the evidence for protein-protein interactions from PubMed abstracts, Bioinformatics, v.22 n.14, p.e220-e226, July 2006 [doi>10.1093/bioinformatics/btl203]
• 8: J. Li, X. Zhang, Y. Hao, M. Huang, and X. Zhu. Learning domain-specific knowledge from context --- THUIR at TREC'2005 genomics track. In Proceedings of 14th Text Retrireval Conference (TREC2005), Gaithersburg, USA, 2005.
• 9: Haibin Liu , Christian Blouin , Vlado Kešelj, Identifying interaction sentences from biological literature using automatically extracted patterns, Proceedings of the Workshop on BioNLP, June 04-05, 2009, Boulder, Colorado
• 10: C. Plake, J. Hakenberg, and U. Leser. Learning patterns for information extraction from free text. In Proceedings of AKKD 2005, Karlsruhe, Germany, 2005.
• 11: A. Skusa, A. Ruegg, and J. Kohler. Extraction of biological interaction networks from scientific literature. Brief Bioinform, 6(3):263--276, September 2005.

INDEX TERMS

Primary Classification:
  I. Computing Methodologies
  I.5 PATTERN RECOGNITION
      I.5.2 Design Methodology
          Subjects: Classifier design and evaluation

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

  I. Computing Methodologies
  I.2 ARTIFICIAL INTELLIGENCE
      I.2.8 Problem Solving, Control Methods, and Search
          Subjects: Heuristic methods
  I.5 PATTERN RECOGNITION
      I.5.2 Design Methodology
          Subjects: Feature evaluation and selection
  I.6 SIMULATION AND MODELING
      I.6.4 Model Validation and Analysis
      I.6.5 Model Development
          Subjects: Modeling methodologies

General Terms:
Algorithms, Design, Performance, Theory