The problem of constrained sequencing of a set of jobs on a conveyor system with the objective of minimizing setup cost is investigated in this paper. A setup cost is associated with extra material, labor, or energy required due to the change of attributes in consecutive jobs at processing stations. A finite set of attributes is considered in this research. Sequencing is constrained by the availability of conveyor junctions. The problem is motivated by the paint purge reduction problem at a major U.S. automotive manufacturer. We first model a diverging junction with a sequence-independent setup cost and predefined attributes as an assignment problem and this model is then extended for a more general situation by relaxing the initial assumptions in various ways.

주요 작물들의 표준유전체, 핵심집단 재분석, 전사체 등의 다양한 NGS 정보가 NCBI와 같은 공개 데이터베이스에 빠르게 축적되고 있다. 현재 NCBI의 SRA(Sequence Read Archive) DB에 등록되어 있는 토마토 유전체(genome) 시퀀싱 데이터만 800건 이상, 파일 크기는 23.5 Tb에 달한다. 그러나 이러한 NGS 데이터로부터 원하는 정보를 추출하기 위해 사용할 수 있는 분석용 대용량 서버 자원 및 빅데이터(big data) 처리 기술이 접목된 생물정보분석 프로그램은 매우 제한적이다. 이에 따라 대용량 서버를 갖추고 있지 않아도 대규모 유전체 데이터를 분석할 수 있도록 Genome Cloud 서버에서 작동하는 웹 기반의 SNP 분석 프로그램을 개발하고, 분석 자동화 컨베이어 QUEUE 시스템을 적용하였다. 이 프로그램은 사용자가 분석하고자 하는 SRA accession을 수집하여 프로그램에 입력하면, 자동으로 NCBI-SRA DB에 접속하여 SRA 파일을 서버로 다운로드하면서 SRA 포맷에서 FASTQ 포맷으로 전환한다. 전환된 FASTQ 파일은 자동으로 SNP 분석 파이프라인에 입력되어 SNP가 추출되고, 결과물은 데이터베이스화 된다. 또한 이 프로그램에는 컨베이어 QUEUE 시스템이 접목되어 IO 버퍼와 같은 시스템 과부하를 막아 효율적으로 분석 파이프라인이 진행된다. 1개 FASTQ 파일이 분석되는 동안, 다음 분석이 진행될 1개 SRA 파일의 다운로드 및 포맷 전환이 자동 진행된다. 위 시스템을 적용하였을 때, 1개 SRA(서열 길이 14Gbp)를 Cloud 서버(16 core CPU, RAM 64Gb 사양)로 다운로드하고 포맷을 전환하는데 약 30분~1시간이 소요되었으며, SNP 분석에는 약 6시간이 소요되었다. Cloud의 장점인 확장성을 적용하여 서버 5대를 병렬로 연결하여 사용할 경우, 500개의 샘플을 한 달 이내에 처리할 수 있을 것으로 예상된다. 현재 약 200여개의 토마토 SRA resequencing 데이터에서 표준유전체 대비 수백만 개의 SNP genotype을 확보하였다. 분석 결과물은 토마토 계통 및 집단 정보를 이용하여 향후 Haplotype, LD 분석 등의 주요 응용 분석을 진행하고, TGsol(http://tgsol.seeders.co.kr)에 데이터베이스로 구축하여 제공하고자 한다.