Chaotic motif sampler: detecting motifs from biological sequences by using chaotic neurodynamics

• Matsuura Takafumi

  Graduate school of Science and Engineering, Saitama University

• Ikeguchi Tohru

  Graduate school of Science and Engineering, Saitama University Brain Science Institute, Saitama University

Abstract

Identification of a region in biological sequences, motif extraction problem (MEP) is solved in bioinformatics. However, the MEP is an NP-hard problem. Therefore, it is almost impossible to obtain an optimal solution within a reasonable time frame. To find near optimal solutions for NP-hard combinatorial optimization problems such as traveling salesman problems, quadratic assignment problems, and vehicle routing problems, chaotic search, which is one of the deterministic approaches, has been proposed and exhibits better performance than stochastic approaches. In this paper, we propose a new alignment method that employs chaotic dynamics to solve the MEPs. It is called the Chaotic Motif Sampler. We show that the performance of the Chaotic Motif Sampler is considerably better than that of the conventional methods such as the Gibbs Site Sampler and the Neighborhood Optimization for Multiple Alignment Discovery.

Journal

• Nonlinear Theory and Its Applications, IEICE

  Nonlinear Theory and Its Applications, IEICE 1 (1), 207-220, 2010

  The Institute of Electronics, Information and Communication Engineers

Keywords

• combinatorial optimization problem
• motif extraction problem
• bioinformatics
• chaotic dynamics
• local multiple alignment

Details

• CRID: 1390282680322073472
• NII Article ID: 130000908385
• DOI: 10.1587/nolta.1.207
• BIBCODE: 2010NTA.....1..207M
• ISSN: 21854106
• Web Site: https://www.jstage.jst.go.jp/article/nolta/1/1/1_1_207/_pdf
• Text Lang: en
• Data Source:
  • JaLC
  • Crossref
  • CiNii Articles
  • KAKEN
• Abstract License Flag: Disallowed