정보과학회 컴퓨팅의 실제 논문지 (KIISE Transactions on Computing Practices)
Current Result Document :
| 한글제목(Korean Title) |
신장 트리 오토마타 기반의 효율적인 Markush 화합물 매칭 알고리즘 |
| 영문제목(English Title) |
An Efficient Matching Algorithm for Markush Structure using Spanning Tree Automata |
| 저자(Author) |
백승엽
천현준
강지연
최형종
한요섭
Seung-Yeop Baik
Hyunjoon Cheon
Ji-Yeon Kang
Hyong-Jong Choi
Yo-Sub Han
|
| 원문수록처(Citation) |
VOL 49 NO. 04 PP. 0262 ~ 0266 (2022. 04) |
한글내용
(Korean Abstract) |
화합물 데이터베이스의 거대화로, 원하는 용도의 화합물을 짧은 시간안에 찾는 문제가 대두되었다. 이와 유사한 문제들을 다루는 화학정보학 분야에서는 Markush 구조를 활용하여 화합물을 표현한다. Markush 구조는 화합물의 구조를 기호화한 그래프 구조로, 하나의 Markush 표현이 수많은 화합물을 표현할 수 있다. 이때 특정 화합물과 Markush 구조 간 포함 여부를 확인하는 과정을 화합물 매칭 판별 과정이라고 한다. 본 연구에서는 화합물 매칭 판별을 위하여 주어진 Markush 구조의 신장 트리에 대한 트리 매칭을 수행하는 신장 트리 오토마타 방법을 활용된다. 기존의 매칭 방법을 보완하여, 최저 높이를 갖는 신장 트리를 생성하고, 매칭을 위한 신장 트리 오토마타를 생성한다. 또한 화합물에서의 반복적 구조를 효율적으로 표현하여 매칭 수행 시간을 고속화하는 방법을 제안한다. 제안하는 알고리즘을 실제 Markush 구조 데이터에 적용하여 2～10%의 매칭 수행시간 향상이 있음을 확인하였다.
|
영문내용
(English Abstract) |
As the number of the chemical compound in the database grows, it becomes increasingly important to develop a fast-searching method for appropriate compounds. Chemoinformatic use Markush structures to express chemical compounds for similar problems. The Markush structure is a simple graph representation for the structure of the compound group. The compound matching is used to determine whether a specific compound belongs to a given Markush structure. The matching problem is known to be PSPACE-complete. For the fast processing in practice, we study a matching method using spanning tree automata, which are useful for denoting Markush structures. We make a spanning tree automaton with lowest height for representing the Markush structure effectively. We propose a fast-matching algorithm by efficiently expressing repetitive structure in a compound. The experimental results confirm that our approach improves the matching process by 10% for practical Markush structures used for chemical compounds. |
| 키워드(Keyword) |
신장 트리 오토마타
Markush 구조
화합물 매칭 판별
markush structure
spanning tree automata
chemical compound matching
|
| 파일첨부 |
PDF 다운로드
|
