분석 프로그램 검색

Study : 1711044752

연구과제 정보

accession,
2014M3C9A3063541
1711044752
멀티 오믹스 분석 알고리즘 및 플랫폼 개발
미래부
서울대학교
김선
2016
2016-11-01     ~      2017-08-31
김선
sunkim.bioinfo@snu.ac.kr
028807280

등록 프로그램 / 파이프라인 / 웹 서비스 정보

accession,

1. 분석 프로그램   2. 대용량 유전체 분석

한글명칭 DNA sequence assembly의 overlap 문제에 대한 알고리즘
영문명칭
프로그램 FastAPSP.tar.gz
매뉴얼 매뉴얼 다운로드
모식도 프로그램 전체 모식도 없음
웹 서비스 주소
주요 내용 특징 생물정보학 분야에서 DNA sequence assembly 문제는 reads 시퀀스의 집합으로부터 하나의 target sequence를 재구성하는 것이다. DNA sequence assembly 문제는 overlap, layout, consensus 3 단계로 진행이 된다. 세 단계 중, overlap은 연산량이 가장 많은 부분으로 전체 연산의 80%를 차지한다. 컴퓨터 이론 분야에서는 overlap 문제를 All-pairs suffix-prefix (APSP) 문제로 정의하고 많은 최적 알고리즘들을 발표하였다. APSP 문제는 k개의 시퀀스가 주어져 있을 때 가능한 모든 쌍의 두 시퀀스에 대하여 한 시퀀스의 prefix이면서 다른 시퀀스의 suffix인 가장 긴 부분 시퀀스를 찾는 문제다. 본 연구팀은 문자열 매칭 알고리즘 분야의 고급 테크닉을 APSP 문제에 도입하여 APSP를 빠르게 계산하는 알고리즘을 제안하고 개발하였다. 실험에는 5개의 real dataset을 사용하여 하였으며 본 연구팀이 개발한 알고리즘 our1, our2를 기존 알고리즘인 SOF, Readjoiner와 비교하였다(om은 계산하는 overlap의 최소 길이를 의미한다). 그 결과 본 연구팀의 알고리즘은 기존 알고리즘인 SOF, ReadJoiner 보다 평균적으로 각각 약 14배, 18배 빠른 결과를 보여주었다.
주요 기능 overlap
사용방법
LINUX
C