标题：The Longest Common Exemplar Subsequence Problem
作者：Zhang, Shu; Wang, Ruizhi; Zhu, Daming; Jiang, Haitao; Feng, Haodi; Guo, Jiong; Liu, Xiaowen
作者机构：[Zhang, Shu; Wang, Ruizhi; Zhu, Daming; Jiang, Haitao; Feng, Haodi; Guo, Jiong] Shandong Univ, Sch Comp Sci & Technol, Jinan, Shandong, Peoples R Chin 更多
会议名称：IEEE International Conference on Bioinformatics and Biomedicine (BIBM)
会议日期：DEC 03-06, 2018
来源：PROCEEDINGS 2018 IEEE INTERNATIONAL CONFERENCE ON BIOINFORMATICS AND BIOMEDICINE (BIBM)
关键词：dynamic programming; algorithm; exemplar subsequence; genome; s-span
摘要：In this paper, we propose to find order conserved subsequences of genomes by finding longest common exemplar subsequences of the genomes. The longest common exemplar subsequence problem is given by two genomes, asks to find a common exemplar subsequence of them, such that the exemplar subsequence length is maximized.; We focus on genomes whose genes of the same gene family are in at most s spans. We propose a dynamic programming algorithm with time complexity O(s4(s) mn) to find a longest common exemplar subsequence of two genomes with one genome admitting s span genes of the same gene family, where m, n stand for the gene numbers of those two given genomes. Our algorithm can be extended to find longest common exemplar subsequences of more than one genomes.