An efficient algorithm to detect common ancestor genes for non-overlapping inversion and applications

作     者：Zohora, Fatema Tuz Rahman, M. Sohel 

作者机构：Bangladesh Univ Engn & Technol Dept CSE AlEDA Grp Dhaka 1000 Bangladesh 

出 版 物：《THEORETICAL COMPUTER SCIENCE》 (理论计算机科学)

年 卷 期：2016年第656卷第PartB期

页      面：188-214页

核心收录：

学科分类：08[工学] 0812[工学-计算机科学与技术（可授工学、理学学位）] 

主　　题：Consensus string Inversion Genetic disease Allelic heterogeneity Iterative algorithm Matrix 

摘      要：In this paper, an algorithm is proposed that detects the existence of common ancestor gene sequences for non-overlapping inversion (reversed complement) metric given two input DNA sequences. Theoretical worst case running time complexity of the algorithm is proven to be O (n(4)), where n is the length of each input sequence. However, by experiment, the running time complexity is found to be O (n(3)) for the worst case and O (n(2)) for average case. Moreover, the worst case occurs when both input sequences have the similarity of around 90% which is very rare. This work is motivated by the purpose of diagnosing an unknown genetic disease that shows allelic heterogeneity, a case where a normal gene mutates in different orders resulting in two different gene sequences causing two different genetic diseases. Our algorithm can potentially save huge energy and cost of the existing diagnostic approaches. The algorithm can be useful as well in the study of breed-related hereditary conditions to determine the genetic spread of a defective gene in the population. (C) 2016 Elsevier B.V. All rights reserved.