Longest Order Conserved Repetition-free Subsequences

Although conserved gene subsequences play a basically necessary part in researches such as biomedicine and bio-breeding, there is short of a practical tool to predict conserved gene subsequences in genomes. We propose a problem that is formalized to find a repetition-free longest common subsequence of given genomes with subsequences identical to indexed gene subsequences. We present an algorithm for this problem that is driven to run faster sufficiently by maintaining those gene families in confusion of their maintainability. The algorithm can be driven to run furthermore faster due to more indexed genes selected. The algorithm based software was examined to quest 23 human/gorilla chromosome summary pairs for solutions whose basic units are annotated as well as pseudo genes, namely consecutive DNA subsequences. The experimental result showed that our algorithm performed better than previous algorithms CMSA and Hyb-CMSA in both time complexity and result length.