등록특허 (51) Int. Cl. 7 G06N 3/08 (19) 대한민국특허청 (KR) (12) 등록특허공보 (B1) (45) 공고일자 (11) 등록번호 (24) 등록일자 2005 년 07 월 27 일 년 07 월 19

Similar documents
특허청구의 범위 청구항 1 복수개의 프리캐스트 콘크리트 부재(1)를 서로 결합하여 연속화시키는 구조로서, 삽입공이 형성되어 있고 상기 삽입공 내면에는 나사부가 형성되어 있는 너트형 고정부재(10)가, 상기 프리캐스 트 콘크리트 부재(1) 내에 내장되도록 배치되는 내부

본 발명은 중공코어 프리캐스트 슬래브 및 그 시공방법에 관한 것으로, 자세하게는 중공코어로 형성된 프리캐스트 슬래브 에 온돌을 일체로 구성한 슬래브 구조 및 그 시공방법에 관한 것이다. 이를 위한 온돌 일체형 중공코어 프리캐스트 슬래브는, 공장에서 제작되는 중공코어 프

Frama-C/JESSIS 사용법 소개

금오공대 컴퓨터공학전공 강의자료

chap x: G입력

학습목차 2.1 다차원배열이란 차원배열의주소와값의참조

PowerPoint 프레젠테이션

(72) 발명자 박세웅 서울특별시관악구신림동산 56-1 서울대학교뉴미디어통신공동연구소 최진구 서울특별시영등포구당산동 2 가대우메종아파트 101 동 909 호 - 2 -

<322EBCF8C8AF28BFACBDC0B9AEC1A6292E687770>

서 인코딩한 데이터를 무선으로 송신하기 위한 무선 송신 수단; 및 통화중 상기 입력 수단으로부터의 음원 데이터 전송신 호에 따라 상기 저장 수단에 저장되어 있는 해당 음원 데이터를 상기 디코딩 수단에 의해 디코딩하고, 상기 디코딩한 음원 데이터와 상기 입력 수단을 통해

PowerPoint Presentation

04 Çмú_±â¼ú±â»ç

248019_ALIS0052.hwp

Microsoft PowerPoint - C++ 5 .pptx

3. 다음은카르노맵의표이다. 논리식을간략화한것은? < 나 > 4. 다음카르노맵을간략화시킨결과는? < >

제 12강 함수수열의 평등수렴

특허청구의범위청구항 1 복수의영상검출부로부터출력되는영상의히스토그램 (histogram) 을계산하는단계 ; 상기복수의영상검출부로부터출력되는영상을히스토그램평활화 (histogram equalization) 하는단계 ; 상기복수의영상검출부중하나의영상검출부를선택하는단계 ; 및

실용신안 등록청구의 범위 청구항 1 톤백마대가 설치될 수 있도록 일정간격을 두고 설치되는 한 쌍의 지지프레임과, 상기 지지프레임과 지지프레임의 상부를 서로 연결하는 한 쌍의 연결프레임과, 상기 연결프레임의 상부에 일정간격을 두고 다수 설치되어 상기 톤백마대와 그 투입구

Microsoft PowerPoint - chap06-2pointer.ppt

많이 이용하는 라면,햄버그,과자,탄산음료등은 무서운 병을 유발하고 비만의 원인 식품 이다. 8,등겨에 흘려 보낸 영양을 되 찾을 수 있다. 도정과정에서 등겨에 흘려 보낸 영양 많은 쌀눈과 쌀껍질의 영양을 등겨를 물에 우러나게하여 장시간 물에 담가 두어 영양을 되 찾는다

Microsoft PowerPoint - ch10 - 이진트리, AVL 트리, 트리 응용 pm0600

Microsoft PowerPoint - chap04-연산자.pptx

11장 포인터

C# Programming Guide - Types

2017 년 6 월한국소프트웨어감정평가학회논문지제 13 권제 1 호 Abstract

슬라이드 1

17장 클래스와 메소드

adfasdfasfdasfasfadf

PowerPoint Presentation

저작자표시 - 비영리 - 변경금지 2.0 대한민국 이용자는아래의조건을따르는경우에한하여자유롭게 이저작물을복제, 배포, 전송, 전시, 공연및방송할수있습니다. 다음과같은조건을따라야합니다 : 저작자표시. 귀하는원저작자를표시하여야합니다. 비영리. 귀하는이저작물을영리목적으로이용할

설계란 무엇인가?

<3235B0AD20BCF6BFADC0C720B1D8C7D120C2FC20B0C5C1FE20322E687770>

특허청구의 범위 청구항 1 앵커(20)를 이용한 옹벽 시공에 사용되는 옹벽패널에 있어서, 단위패널형태의 판 형태로 구성되며, 내부 중앙부가 후방 하부를 향해 기울어지도록 돌출 형성되어, 전면이 오 목하게 들어가고 후면이 돌출된 결속부(11)를 형성하되, 이 결속부(11

Microsoft PowerPoint - ch07 - 포인터 pm0415

PowerPoint 프레젠테이션

#편집인협회보381호_0422

슬라이드 1

5장. JSP와 Servlet 프로그래밍을 위한 기본 문법(완성-0421).hwp

[ 마이크로프로세서 1] 2 주차 3 차시. 포인터와구조체 2 주차 3 차시포인터와구조체 학습목표 1. C 언어에서가장어려운포인터와구조체를설명할수있다. 2. Call By Value 와 Call By Reference 를구분할수있다. 학습내용 1 : 함수 (Functi

이 발명을 지원한 국가연구개발사업 과제고유번호 A 부처명 지식경제부 연구관리전문기관 연구사업명 IT핵심기술개발 연구과제명 융합형 포털서비스를 위한 이용자 참여형 방송기술개발 기여율 주관기관 전자부품연구원 연구기간 2008년 03월 01일 ~ 2

실험 5

임베디드시스템설계강의자료 6 system call 2/2 (2014 년도 1 학기 ) 김영진 아주대학교전자공학과

설계란 무엇인가?

<4D F736F F F696E74202D203137C0E55FBFACBDC0B9AEC1A6BCD6B7E7BCC72E707074>

딥러닝 첫걸음

Chap 6: Graphs

(72) 발명자 정종수 서울특별시 서대문구 모래내로 319, 101동 405호 (홍은동, 진흥아파트) 김정환 서울특별시 구로구 구로동로21길 7 (구로동) - 2 -

쉽게 풀어쓴 C 프로그래밍

Microsoft PowerPoint - additional01.ppt [호환 모드]

슬라이드 1

Microsoft PowerPoint - chap05-제어문.pptx

(72) 발명자 김도규 서울특별시성북구장위 3 동 박준일 서울특별시강서구등촌동 서광아파트 103 동 803 호 유형규 경기도광명시광명 4 동한진아파트 101 동 1801 호 - 2 -

슬라이드 1

DBMS & SQL Server Installation Database Laboratory

OCW_C언어 기초

Chap 6: Graphs

Microsoft PowerPoint - chap06-1Array.ppt

슬라이드 1

01장.자료구조와 알고리즘

C++ Programming

슬라이드 1

쉽게 풀어쓴 C 프로그래밍

(72) 발명자 오인환 서울 노원구 중계로 195, 101동 803호 (중계동, 신 안동진아파트) 서혜리 서울 종로구 평창14길 23, (평창동) 한훈식 서울 강남구 언주로71길 25-5, 301호 (역삼동, 영 훈하이츠) 이 발명을 지원한 국가연구개발사업 과제고유번호

3.2 함수의정의 Theorem 6 함수 f : X Y 와 Y W 인집합 W 에대하여 f : X W 는함수이다. Proof. f : X Y 가함수이므로 f X Y 이고, Y W 이므로 f X W 이므로 F0이만족된다. 함수의정의 F1, F2은 f : X Y 가함수이므로

다. 여기서, TFTP 을통해파일을가져온 (TFTP GetFile) 후에 SNMP 을통해관리정보베이스 (Management Information Base : MIB) 설정요구 (SNMP SetRequest MIB) 가네트웍요소로내려가려면, 로그가데이터베이스에쓰여진 (w

chap 5: Trees

강의 개요

특허청구의 범위 청구항 1 지그비 통신 망에서 지그비 노드들의 우선 순위를 부여하는 방법에 있어서, (a) 상기 지그비 노드들 각각의 CCA 수행 시간들을 전송할 데이터의 우선 순위에 따라 가변시키는 단계와; (b) 상기 가변되는 CCA 수행 시간들은 우선 순위가 높은

슬라이드 1

PowerPoint 프레젠테이션

2002년 2학기 자료구조

슬라이드 1

프로그래밍개론및실습 2015 년 2 학기프로그래밍개론및실습과목으로본내용은강의교재인생능출판사, 두근두근 C 언어수업, 천인국지음을발췌수정하였음

PowerPoint 프레젠테이션

HW5 Exercise 1 (60pts) M interpreter with a simple type system M. M. M.., M (simple type system). M, M. M., M.

2016 학년도약학대학면접문제해설 문제 2 아래의질문에 3-4분이내로답하시오. 표피성장인자수용체 (epidermal growth factor receptor, EGFR) 는수용체티로신인산화효소군 (receptor tyrosine kinases, RTKs) 의일종으로서세

특허청구의 범위 청구항 1 맨홀 일부분에 관통되게 결합되는 맨홀결합구와; 상기 맨홀결합구의 전방에 연통되게 형성되어 토양속에 묻히게 설치되고, 외주면에는 지하수가 유입될 수 있는 다수의 통공이 관통 형성된 지하수유입구와; 상기 맨홀결합구의 후방에 연통되고 수직으로 세워

Microsoft PowerPoint - chap-11.pptx

특허청구의 범위 청구항 1 고유한 USB-ID를 가지며, 강제 포맷이나 프로그램 삭제가 불가능한 CD영역과 데이터의 읽기, 쓰기가 가능한 일 반영역으로 분할되어 있고 상기 CD영역에 임산부 도우미 프로그램이 임산부 PC(200)에 연결되면 자동 설치 및 실행되게 탑재된

제 3강 역함수의 미분과 로피탈의 정리


COVER.HWP

이슈분석 2000 Vol.1

가볍게읽는-내지-1-2

kbs_thesis.hwp


untitled

한눈에-아세안 내지-1

PowerPoint 프레젠테이션

PowerPoint Template

표본재추출(resampling) 방법


PowerPoint Presentation

DBPIA-NURIMEDIA

학습목표 함수프로시저, 서브프로시저의의미를안다. 매개변수전달방식을학습한다. 함수를이용한프로그래밍한다. 2

완벽한개념정립 _ 행렬의참, 거짓 수학전문가 NAMU 선생 1. 행렬의참, 거짓개념정리 1. 교환법칙과관련한내용, 는항상성립하지만 는항상성립하지는않는다. < 참인명제 > (1),, (2) ( ) 인경우에는 가성립한다.,,, (3) 다음과같은관계식을만족하는두행렬 A,B에

한것으로스마트단말기에의하여드론조종앱을설치하는제 1 단계 ; 스마트단말기에의하여드론의불루투스통 신부에부여된고유식별번호를입력저장하고드론의불루투스를인식하며드론의블루투스통신부로부터회신되 는신호의수신레벨을분석하여최대통신거리를확인하여저장하는제 2 단계 ; 스마트단말기에의하여최대통

03_queue

<4D F736F F F696E74202D20C1A63036C0E520BCB1C5C3B0FA20B9DDBAB928B0ADC0C729205BC8A3C8AF20B8F0B5E55D>

PowerPoint 프레젠테이션

Transcription:

(51) Int. Cl. 7 G06N 3/08 (19) 대한민국특허청 (KR) (12) 등록특허공보 (B1) (45) 공고일자 (11) 등록번호 (24) 등록일자 2005 년 07 월 27 일 10-0504039 2005 년 07 월 19 일 (21) 출원번호 10-2003-0060424 (65) 공개번호 10-2005-0022133 (22) 출원일자 2003년08월29일 (43) 공개일자 2005년03월07일 (73) 특허권자재단법인서울대학교산학협력재단서울특별시관악구봉천동산 4-2 (72) 발명자장병탁서울서초구방배 3 동방배아트힐 101-1801 (74) 대리인임재룡 심사관 : 마정윤 남진우경기도안산시본오 3 동 1123-4 402 호 (54) ncrna 서열의컴퓨터적동정방법 정제균서울특별시관악구봉천 6 동우성아파트 105 동 1003 호 요약 본발명은진화알고리즘의하나인유전자프로그래밍기법을이용하는 ncrna ( 비코딩 RNA), 특히 mirna 의컴퓨터적동정방법에관한것으로, 더욱구체적으로본발명에따른 ncrna, 특히 mirna 의컴퓨터적동정방법은 ncrna, 특히 mirna 인것으로공지된포지티브데이터세트및 ncrna, 특히 mirna 가아닌것으로공지된네거티브데이터세트로이루어진데이터세트로부터폴스네거티브 (false-negative) 결과를생성하지않는함수트리와이로부터전환된 RNA 공통구조문법을유전자프로그래밍 (genetic programming) 으로진화적으로학습시켜생성된최적의함수트리또는 RNA 공통구조문법 (RCSG) 에, 공지되지않은서열을적용하여, 상기비공지서열이 ncrna, 특히 mirna 인지의여부를확인하는것을포함함을특징으로한다. 또한, 본발명에따른방법은 mirna 뿐만아니라, 일반적으로 ncrna 를모두예측할수있는방법으로서사용될수있다. 대표도 도 2 색인어 mirna 전구체, mirna, 유전자프로그래밍, RNA 공통구조문법, EM 알고리즘, 공통구조학습, ncrna 명세서 도면의간단한설명 도 1 은유전자프로그래밍을이용한 RCSG(RNA 공통구조문법 ) 의학습과 mirna 예측을위한전체알고리즘의구조를나타낸다. 도 2 는유전자프로그래밍을이용한 RNA 염기서열로부터 RCSG 의학습과목표 RNA 후보탐색과정을나타낸다. - 1 -

도 3 은목표 RNA 후보중에서 EM 알고리즘을이용하여학습한스코어모델을이용한 2 차탐색과정및 mirna 에대한스코어모델을나타낸다. 도 4 는 RNA 구조문법을유전자프로그래밍에적용하기위해트리구조로변환하는방법과각트리의함수구성의일례를나타낸다. 도 5 는기존의유전자프로그래밍알고리즘을나타낸다. 도 6 은염기의한문자코드및그의상보적염기를나타낸다. 도 7 은유전자프로그래밍에의해학습된 mirna 전구체의 RNA 공통구조문법 (RCSG) 의일례를나타낸다. 도 8 은 EM 알고리즘에의해학습된 mirna 전구체의스코어모델에대하여훈련데이터및테스트데이터를사용한검증한결과를나타낸다. 발명의상세한설명 발명의목적 발명이속하는기술및그분야의종래기술 본발명은대량의유전체데이터속에서구조적으로유사한 ncrna, 특히 mirna 전구체를발굴하기위해진화알고리즘의기법중하나인유전자프로그래밍을이용하여 RNA 공통구조문법 (RCSG) 을학습하고, 학습된 RNA 공통구조문법을이용하여유전체데이터내에서 ncrna 의한종류인 mirna 전구체를발굴하는기술에관한것이다. 또한, 본발명에따른방법은 mirna 뿐만아니라, 일반적으로 ncrna 를모두예측할수있는방법으로서사용될수있다. mirna 는세포내에서유전자의전사를중지시킴으로써유전자의발현을직접적으로조절하게되는작은 RNA 집단중의하나이다. 따라서, 유전체데이터에서 mirna 를동정해내는작업은생물학적으로상당히중요한것으로당업계에서여겨지고있으며, 이에 mirna 의예측방법및동정방법에대한연구가전세계적으로이루어지고있다. 그러나, 수많은유전자서열을포함하고있는유전체데이터중의서열하나하나에대해서실험적으로 mirna 를동정해내는작업은엄청난시간의소요와실험경비로인해, 유전체데이터에서 mirna 를정확하고신속하게동정해낼수있는알고리즘의개발이요구되고있으며, 이러한알고리즘은생물학적실험에서의시간과경비를상당히절감할수있으며, 생물학적으로 mirna 를동정하는많은어려움을덜어줄수있다 이러한목적하에초기에개발된것으로서, RNA 의 1 차염기서열에기초하여계산학적으로 mirna 를동정하는방법은 1 차염기서열상의통계적인중요도가부족하고, 따라서유전자또는 RNA 의 1 차핵산서열의상동성에분석에기초하여유전자또는 RNA 의기능을분석해내는기존의유전자예측알고리즘을적용하기에는어려움이있다. 즉, mirna 전구체의유사종의유사 mirna 에존재하는통계적데이터를분석하여유사한 mirna 를예측하는방법은유사종이존재하지않아통계적인데이터를만들지못한다면가능하지않는방법이다. 따라서, mirna 의경우염기서열보다는 2 차구조에기초한 mirna 의동정방법에대한요구가당업계에존재하여왔다. 종래에 mirna 와같은 ncrna ( 단백질로코딩되지않는 RNA; non-coding RNA) 의 2 차구조에서공통적인구조정보를추출하는방법에는크게두가지접근방법이주목받았다. 하나는 RNA 의 2 차구조의유사성을직접적으로분석할수있는구조얼라인먼트 (Structural alignment) 방법이며, 다른하나는여러개의염기서열이주어졌을때상동성이높은모티프 (motif) 를찾기위해 Hidden Makov Model (HMMs) 방법을사용하는것처럼, 여러개의 RNA 가주어졌을때구조적상동성을갖는모델을학습하는방법이다. 발명이이루고자하는기술적과제 본발명자들또한상당한비용과시간을요구하는실험적 ncrna, 특히 mirna 의동정방법을대체하는 ncrna, 특히 mirna 의계산학적동정방법을개발하고자하였으며, 특히 mirna 들간의염기서열의유사성이낮기때문에종래에이용하기에부적절했던 1 차염기서열에기초하여수행되었던통계학적 mirna 의분석방법을개선하기위해 RNA 의 2 차구조에기초한 mirna 의계산학적동정방법을개발하고자하였다. 특히, mirna 의전구체가약 70bp 정도의헤어핀 (hairpin) 구조를가지고있다고알려져있을지라도, 다른 ncrna 와는달리 mirna 전구체의공통적인구조는종간특이성이조금떨어지기때문에, 상대적으로종계열적으로거리가먼종들간에는구조에중요한서열간의유사성에기인한 mirna 의동정방법에는한계가있다. 본발명자들은이러한한계점을극복할수있는 mirna 의계산학적동정방법을개발하고자하였다. 따라서, 본발명은새로운 mirna 의계산학적동정방법을제공하는것이다. 또한, 본발명에따른 mirna 의계산학적동정방법은대량의유전체데이터로부터 mirna 전구체또는 mirna 만을특이성높게신속히선별해내는것을목적으로한다. 발명의구성및작용 - 2 -

상기한목적을달성하기위하여, 본발명에따른 ncrna, 특히 mirna 의컴퓨터적동정방법은 ncrna (non-coding RNA), 특히 mirna 인것으로공지된포지티브데이터세트및 ncrna, 특히 mirna 가아닌것으로공지된네거티브데이터세트로이루어진데이터세트로부터폴스네거티브 (false-negative) 결과를생성하지않는함수트리와이로부터전환된 RNA 공통구조문법을유전자프로그래밍 (genetic programming) 으로진화적으로학습시켜생성된최적의함수트리또는 RNA 공통구조문법 (RCSG) 에, 공지되지않은서열을적용하여, 상기비공지서열이 mirna 인지의여부를확인하는것을포함함을특징으로한다. 특히, 본발명에따른 ncrna 의컴퓨터적동정방법은 mirna 의 ncrna 의컴퓨터적동정방법으로서특히유용하다. 이하, 본발명을더욱구체적으로설명한다. 본발명에따른 ncrna 의컴퓨터적동정방법은하기단계를포함함을특징으로하는 mirna 서열의컴퓨터적동정방법 : (1) 함수트리를포함하는초기집단을랜덤하게생성하는단계 ; (2) 상기모든함수트리를구조문법으로전환하는단계 ; (3) 공지된포지티브데이터세트및공지된네거티브데이터세트를이용하여, 상기모든구조문법을 RNA 모티프검색을통해평가하는단계 ; (4) 모든구조문법에대해적합도, 특이도, 민감도및복잡도를계산하는단계 ; (5) 상기최적도를갖는구조문법을함수트리로전환하는단계 ; (6) 선택된함수트리를돌연변이및교배를통해변형시키는단계 ; (7) 상기변형을갖는후세대함수트리를생성하고, 최적의개체를선택하는단계 ; 및 (8) 적합도, 특이도, 민감도및복잡도를갖는함수트리가생성될때까지, 상기단계 (2) 내지 (7) 을반복하는단계. 상기각단계에서사용된용어들, 즉 " 함수트리 ", " 구조문법 ", " 포지티브데이터 ", " 네거티브데이터 ", "RNA 모티프검색 ", " 적합도 ", " 특이도 ", " 민감도 ", " 복잡도 ", " 돌연변이 ", " 후세대 " 및 " 교배 " 는유전자프로그래밍분야및 RNA 모티프구조를통한 RNA 의 2 차구조를분석하는분야에서통상적으로사용되는용어로서, 본발명에서상기용어는당업계에서의미하는범주와동일한의미를갖는다. 예를들어, 본원에서사용된용어 " 함수 " 는하나이상의변수들을적절하게연산하여연산결과값, 즉함수값에대응시키는연산자를의미한다. 본원에서사용된용어 " 함수트리 " 는유전자프로그래밍기법의특징으로, 기본적인함수들을트리구조의각교차지점, 즉노드에위치시켜변수들의연산순서및방식에대해서정의한함수군을의미한다. 각각의함수트리는일반적으로 " 개체 " 라불린다. 본원에서사용된용어 " 구조문법 " 은상기함수트리를컴퓨터가인식할수있는프로그래밍언어로표현된것을의미한다. 이러한구조문법은유전자프로그램에서 " 프로그램 " 이라한다. 또한, 본발명에서는 RNA 의공통구조를학습하므로, 이러한프로그램을 "RNA 공통구조문법 (RCSG)", "RNA 구조문법 " 또는 " 구조문법 " 이라한다. 본원에서사용된용어 " 포지티브데이터 " 및 " 네거티브데이터 " 는각각 ncrna, 특히 mirna 인데이터군과아닌것으로알려진데이터군을의미한다. " 폴스네거티브 " 란용어는포지티브데이터이지만, 생성된 RNA 공통구조문법에의해네거티브데이터인것으로판명되었을경우, 이데이터를폴스네거티브라한다. 본원에서사용된용어 "RNA 모티프 " 는 RNA 의 2 차구조를생성함에있어서구조적으로반복적으로나타나는서열, 서열길이, 미스매치서열등의패턴에관한것이다. 본원에서사용된용어 " 적합도 " 는함수트리가얼마나정확하게 ncrna, 특히 mirna 를동정해낼수있는지를알려주는지수이다. 본원에서사용된용어 " 특이도 ", " 민감도 " 및 " 복잡도 " 는유전자프로그래밍에의해서얻어진최적의함수트리가유전계통적으로거리가먼종유래의미동정 mirna 데이터들에대해서정확하고일반적으로동정결과를얻어낼수있는지를평가하기위해사용되는지수이다. 용어 " 돌연변이 " 및 " 교배 " 는함수트리를변형시키는기법으로함수트리의일부를변형시키거나서로의일부함수트리를바꾸는것을의미한다. 용어 " 후세대 " 는돌연변이및교배를수행한이후에생성된함수트리에대해서일컫는자손함수트리를의미한다. - 3 -

mirna 와같은 ncrna 의 2 차구조에서공통적인구조정보를추출하는방법에는크게두가지접근방법을생각할수있다. 첫번째는 RNA 의 2 차구조의유사성을직접적으로분석할수있는구조적정렬방법이다. 두번째는여러개의염기서열이주어졌을때상동성이높은모티프를찾기위해 HMMs 방법을사용하는것처럼, 특정기능이공지된여러개의 RNA 가주어졌을때구조적상동성을갖는모델을학습하는방법이다. 본발명은진화알고리즘의하나인유전자프로그래밍을사용하여 RNA 구조의상동성을학습하는두번째방법으로, 도 4 에서나타낸바와같은전략을사용하였다. 본발명에따른 ncrna, 특히 mirna 의컴퓨터적동정에사용되는유전자프로그래밍은, (i) 랜덤한초기집단의생성 ; (ii) mirna 인지의여부가이미판명된 RNA 데이터서열을이용하여상기초기집단으로부터폴스네거티브를생성하지않는개체의선택 ; (iii) 상기개체에대한최적도 (fitness) 평가 ; (iv) 상기함수집단의임의의변형후, 상기단계 (ii) 내지 (iv) 의반복을포함한다. 우선, 초기집단의임의적인생성에대하여설명한다. 초기집단은하기기재된함수및변수의사용에대한몇가지제한점을가지면서랜덤하게생성된다. 따라서, 초기집단의생성에있어서, 노드의수, 함수트리의폭에있어서특별한제한은없다. 그러나, 함수트리가복잡해지는것을방지하기위하여, 하기기재된복잡도계산식에적합한노드수및함수트리의폭을갖는것이바람직하다. ii) mirna 인지의여부가이미판명된데이터서열을이용하여상기초기집단으로부터폴스네거티브를생성하지않는개체의선택을선택하기위해사용되는, 그구조가알려진 RNA 들은 mirna 이거나그렇지않은각종구조, 예컨대선형, 헤어핀, mirna 전구체, RNA 슈도녹 (pseudoknot), 철반응요소 (iron response element), 연속적인헤어핀 (consecutive hairpin), 불지 (bulge) 및내부루프 (internal loop), rrna 및 mrna 절편의구조등을포함한다. 한편, 유전자프로그래밍은유전자프로그램에해당되는개체를트리형식으로표현하며, 표현된개체들에대해서돌연변이 (Mutation) 나교차 (Crossover) 와같은변이를주어서세대가반복함에따라주어진적합도함수 (Fitness function) 에근사함으로써자동적으로주어진데이터를학습하는알고리즘을갖는다. 본발명에서는유전자프로그램에해당하는각트리의노드를 RNA 구조로표현할수있는재귀적함수로정의하여 RNA 구조문법을학습한다. 이를위해, 본발명은구조적문법으로표현가능한 RNA 구조를트리구조로변형할수있는적당한규칙을적용한다. 이에대해서는하기에설명한다. 본발명에따르면, RNA 구조문법을유전자프로그래밍으로학습하기위해트리구조로변환하는규칙을적용하고, 이러한방식으로얻어진트리구조를학습을위해공통구조문법으로전환시켜, 유전자프로그래밍을통해학습된 RCSG 를이용하여, 검색된미동정 mirna 전구체후보들속에서실제특이성이높은 mirna 전구체를개발할수있다. 한편, 본발명에따른방법은상기에서함수트리의 RNA 구조문법으로의전환이컴퓨터적으로자동적으로생성될수있는시스템을갖는다. 따라서, 본발명에따른방법은, 유전자프로그래밍을통해전문가조차도쉽게설계하기어려운 RNA 의구조문법을손쉽게자동적으로생성할수있다. 본발명자들은, 첫번째로 RNAmotif 프로그램 (T. J. Macke et al., 2001, Nucleic Acids Research) 에서정의한 RNA 구조문법을트리구조로자동적으로바꿀수있는방법을개발하였다. 트리의내부노드에는 f1, f2 의함수로정의되며, f1, f2 함수는문법을재귀적으로표현하게된다. 또한각내부노드에는 RNA 구조문법이가질수있는변수 minlen/maxlen, len, mispair, seq, mismatch 를포함하고있다 ( 도 4 참조 ). 이때, minlen/maxlen 과 len 은나선 (helix) 구조의길이를나타내고 ; seq 는 RNA 구조에포함되는염기서열의조각의정보를나타내며 ; mismatch 는염기서열정보중일치하지않아도되는염기서열의수를의미한다. 본발명에서는유전자프로그래밍을통해변이를주게될때, RNA 구조문법에서이탈되지않도록몇가지제약사항을적용한다. 즉, 말단노드에는항상 f2 함수가오게하고, f2 함수가동시에연속해서나올수없도록한다. 또한, minlen/maxlen 변수는동시에있어야하며, len 변수와는동시에올수없도록한다. 본발명자들은, 둘째로, 트리로표현된 RNA 구조문법을유전자프로그래밍에적용하기위해서는도 5 에서보여진일반적인유전자프로그래밍과조금다른알고리즘이필요로한다. 따라서, 본발명에서는일반적인유전자프로그래밍에서변형된알고리즘, 하기와같은알고리즘을사용하고있다. 1. 함수트리의초기집단생성 2. 함수트리의구조문법으로의전환 3. RNA 모티프의평가 3.1. X 세대에서국지적탐색 (local search) 4. 모은새로운개체가생성될때까지하기단계를반복 4.1. 최적의적합도를갖는함수트리를새로운집단에첨가 4.2. 상위 50% 선택 4.3. 선택된트리의변형 ( 교배및돌연변이기법에의해 ) - 4 -

4.4. 변형된함수트리를새로운집단에첨가 5. 최종조건에도달할경우, 전 ( 前 ) 집단을새로운집단으로바꾸고, 상기단계 1 내지 2. 내지 5 를반복. 6. 비동정 7mer 에대해서국지적탐색. 한편, 트리구조의교차변이는같은함수를갖는노드끼리만가능하게하여잘못된문법이생성되는것을막았으며, 적합도함수를계산하기위해 RNA 구조문법과트리구조를자동적으로바꾸는알고리즘을첨가하였다. 또한, 말단노드에는수치적인값대신 f2 함수만을배치되도록하여, 구조적인학습을유도하였다. 1 세대의초기화는무작위적으로생성하게되며, 정해진적합도함수에의해반환된값에의해순위선택을하게된다. 여기서, 최고적합도를갖는개체는다음세대에변이없이전달되도록하였다. 개체의변이시에는변수의값을쁘아종분포 (possoin distribution) 에따라시행여부를결정하도록하였으며, 사용자가정의한변이범위내에서변수값을변경하게된다. 또한, 최적의변수값을찾기위해본발명은각세대별로우수한적합도를갖는문법의변수를세밀히바꾸어가며국지탐색을하였다. 마지막으로 RNA 구조뿐만아니라염기서열에대한국지탐색을위해훈련데이터에서추출한 7bp (7mer 라고도함 ) 의염기서열단어를무작위적으로할당하여학습되도록설계하였다. 또한, 본발명자들은, 세번째로, 트리구조로표현된 RNA 구조문법에서공통된구조문법을자동으로학습하기위해적합도함수를만들었다 [ 하기, 수학식 1 및수학식 2 참조 ]. 이적합도함수는각세대에서생성된 RNA 구조문법이 RNAmotif 프로그램에의해서포지티브데이터와네거티브데이터에서일치하는개수를이용하여계산한특이성과민감도를이용한다. 또한, 트리의노드수와깊이를이용해얻은복잡도를적합도함수에적용함으로써트리의구조가너무작거나커지는것을막아적절하게조절하도록하였다 [ 수학식 3 및수학식 4 참조 ]. 또한, 특이도와민감도에각각상수 spc 와 stc 를곱하여적합도함수에서특이도와민감도에대한균형을조절하도록하였다. 수학식 1 적합도 =spc 특이도 +stc 민감도 + 복잡도 수학식 2 spc+stc=1 수학식 3 수학식 4 단, icomp : i 세대에서그개체의복잡도 bestcomp : 그세대에서최고적합도를갖는개체의복잡도 i: 유전자프로그래밍이거치는세대수 또한, 하기표 1 에서와같이 TP (true positive), FP (false positive), FN (false nagative) 및 TN (true negative) 에대한수를이용하여하기수학식 5, 수학식 6 및수학식 7 에서나타낸바와같이, 특이도및민감도를계산하였다. 예상 + 예상 - 표 1. 실제 + 실제 - TP FP FN TN - 5 -

수학식 5 수학식 6 한편, 하기의 CC 는실제값과예상된값이얼마나잘일치하는지를보여주는상관계수이다. 이상관계수는 0 내지 1 사이의값을갖는다. 수학식 7 이렇게해서학습된 RNA 공통구조문법 (RCSG) 을이용하여대량의데이터에서새로운 RNA 유전자의후보를탐색할수있다. 물론학습된 RCSG 의특이도가상당히높다면, 탐색의결과가최종의결과가될수있다. 하지만, 특이도가높은 RCSG 가학습되지않았다면, 탐색된 RNA 유전자후보중실제찾고자하는목표인것만을골라내는 2 차탐색작업을하게된다. 마지막으로, 본발명에서는 mirna 전구체에대한 2 차탐색작업을위해, mirna 전구체에대한스코어모델을만들었다 ( 도 7 참조 ). 이모델의학습은 EM 알고리즘을이용하여, 학습을위해주어진각 mirna 전구체 n 개에대해서 i=1 부터전구체사이즈의 i=l 까지의트랜지션스코어 (S i,j ) 와페어링스코어 (P i,j ) 를더해나가는아래수학식 8 을최대화하는방향으로진행되었다. 수학식 8 이때각트랜지션스코어 (transition score) 와페어링스코어 (paring score) 는사용자가정의한상수 At, Ap 에의해서비율을결정하며이상수에의해서서열이모호도코드 (ambiguity code) [ 도 6; 모호도코드는한위치에염기서열 A, C, G, T 중두개이상의염기서열이올수있을때사용한다. 예를들어한위치에 C 와 T 가동시에올수있다면모호도코드 "Y" 로표시할수있다. 또한한위치에모든염기가올수있다면 "N" 으로표시할수있다. 이렇게여러개의염기서열이한위치에올수있을때, A,C,G,T 를제외한나머지알파벳중하나로표시한모호도코드로나타낼수있다.] 로학습되는경향이결정된다. 즉 At, Ap 의상수값이클수록 EM 알고리즘에의해학습되는모델의염기서열이모호도코드로학습되는경향을보이게된다. 실시예 본실시예에서수행하는 mirna 예측은두부분으로되어있다. - 알려진 mirna 염기서열로부터 RNA 공통구조문법 (RCSG) 생성 [ 도 7] - mirna 2 차선별을위한 mirna 전구체모델학습과모델을이용한 mirna 전구체탐색의효율 [ 도 8, 3] RCSG 를학습하기위해서이미알려진사람의 mirna 전구체 137 개의양성데이터와 mirna 전구체가아닌다른 ncrna 와 mrna 염기서열에서선택한 290 개의음성데이터를사용하였다. 이두데이터는 RNAmotif 의탐색을통한적합도계산에사용되어, 궁극적으로 RCSG 가최적화되도록안내한다. 이렇게학습된 RCSG 가도 7 에표시되어있으며구조와염기서열이동시에학습된것을볼수있다. 학습된 RCSG 를이용하여사람의인트론데이터베이스내에서 mirna 전구체와유사한후보들을선별한다. - 6 -

다음사람의 134 개 mirna 전구체중 70 개를 EM 알고리즘을이용한스코어모델학습의데이터로사용하였으며음성데이터로사람이 EST 염기서열에서 mirna 전구체와유사한구조를가진데이터 1000 개를추출하여사용하였다. 이렇게학습된 score 모델이도 3 에나타나있으며, At Ap 를각각 0.4 로하여모호도코드 (ambiguity code) 경향을결정한것이다. 모호도코드가많을수록학습된모델이일반적인것이되며, 적을수록특이도를갖는모델이다. 이렇게학습된모델을이용해테스트를위해남겨둔 67 개의 mirna 전구체데이터와실험쥐 (mouse) 의 mirna 전구체데이터에대한사용하였다. 테스트에대한결과를도 8 에보여주고있으며, 우리가학습한모델이 mirna 전구체들을잘예측하고있음을보여주고있다. 발명의효과 이상에서살펴본바와같이, 본발명에따른 mirna 의컴퓨터적동정방법은 mirna 인것으로공지된포지티브데이터세트및 mirna 가아닌것으로공지된네거티브데이터세트인것으로이루어진데이터세트로부터폴스네거티브 (false-negative) 결과를생성하지않는함수트리와이로부터전환된 RNA 공통구조문법을유전자프로그래밍 (genetic programming) 으로진화적으로학습시켜생성된최적의함수트리및 RNA 공통구조문법 (RCSG) 에, 공지되지않은서열을적용하여, 상기비공지서열이 mirna 인지의여부를확인하는함으로써, 정확하고우수한 mirna 예측을수행할수있다. 또한, 이러한방법에의해서, mirna 뿐만아니라, 일반적으로 ncrna 를모두예측할수있는방법으로서사용될수있다. (57) 청구의범위 청구항 1. ncrna (non-coding RNA) 인것으로공지된포지티브데이터세트및 ncrna 가아닌것으로공지된네거티브데이터세트인것으로이루어진데이터세트로부터폴스네거티브 (false-negative) 결과를생성하지않는함수트리와이로부터전환된 RNA 공통구조문법을유전자프로그래밍 (genetic programming) 으로진화적으로학습시켜생성된최적의함수트리및 RNA 공통구조문법 (RCSG) 에, 공지되지않은서열을적용하여, 상기비공지서열이 mirna 인지의여부를확인하는것을포함함을특징으로하는, ncrna 서열의컴퓨터적동정방법. 청구항 2. 제 1 항에있어서, 상기 ncrna 가 mirna (microrna) 인것을특징으로하는 ncrna 서열의컴퓨터적동정방법. 청구항 3. 제 2 항에있어서, 하기단계를포함함을특징으로하는 mirna 서열의컴퓨터적동정방법 : (1) 함수트리를포함하는초기집단을랜덤하게생성하는단계 ; (2) 상기모든함수트리를구조문법으로전환하는단계 ; (3) 공지된포지티브데이터세트및공지된네거티브데이터세트를이용하여, 상기모든구조문법을 RNA 모티프검색을통해평가하는단계 ; (4) 모든구조문법에대해적합도, 특이도, 민감도및복잡도를계산하는단계 ; (5) 상기최적도를구조문법을함수트리로전환하는단계 ; (6) 선택된함수트리를돌연변이및교배를통해변형시키는단계 ; (7) 상기변형을갖는후세대함수트리를생성하고, 최적의개체를선택하는단계 ; 및 (8) 적합도, 특이도, 민감도및복잡도를갖는함수트리가생성될때까지, 상기단계 (2) 내지 (7) 을반복하는단계. 청구항 4. 제 3 항에있어서, 상기단계 (2) 및단계 (5) 에서, 함수트리의구조문법으로의전환또는구조문법의함수트리로의전환이컴퓨터프로그램에의해자동적으로수행됨을특징으로하는 ncrna 서열의컴퓨터적동정방법. 청구항 5. - 7 -

제 3 항에있어서, RNA 구조와염기서열의공통성이유전자프로그래밍에의해동시에학습됨을특징으로하는 ncrna 서열의컴퓨터적동정방법. 청구항 6. 제 1 항에있어서, EM 알고리즘을이용해학습된스코어모델을이용하여 2 차선별을통해 mirna 전구체를예측함을특징으로하는 ncrna 서열의컴퓨터적동정방법. 도면 도면 1 도면 2 도면 3-8 -

도면 4 도면 5-9 -

도면 6 도면 7-10 -

도면 8-11 -