Á¤º¸°úÇÐȸ ÄÄÇ»ÆÃÀÇ ½ÇÁ¦ ³í¹®Áö (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 ´Ù¿î·Îµå
|