Advertisement
Published in:
2012 | OriginalPaper | Chapter
Algorithms with Restrictive Input Constrains on Genome Exemplar Distance Caculation
Authors : Yehong Chen, Daming Zhu, Weifang Tang, Qi Chen, Jie Zhang
Published in: Business, Economics, Financial Sciences, and Management
Publisher: Springer Berlin Heidelberg
Activate our intelligent search to find suitable subject content or patents.
Select sections of text to find matching patents with Artificial Intelligence. powered by
Select sections of text to find additional relevant content using AI-assisted search. powered by
The comparative study of gene order rearrangements has been restricted to the case when the genes in one genome are homologous to at most one gene in the other genome. Sankoff (1999) proposes the estimation of true exemplars, a selection of one gene from each gene family in both genomes such that the distance between the resulting exemplar strings is minimized, which is called exemplar distance. David Bryant in his paper show that the calculation of the exemplar distance between two genomes is NP-hard for both the signed reversals distance and the breakpoint distance, even with quite restrictive conditions on the input. Limite the input according to strictive conditions used by David Bryants’ proof, here we provides two algorithm to solve problem under some input conditions. one is branch and bound algorithms ,the other is Greedy Algorithm for both distances .different DATA can use different Algorithm to get better performance.