TAILIEUCHUNG - Báo cáo sinh học: " Listing all sorting reversals in quadratic time"

Tuyển tập các báo cáo nghiên cứu về sinh học được đăng trên tạp chí y học Molecular Biology cung cấp cho các bạn kiến thức về ngành sinh học đề tài: Listing all sorting reversals in quadratic time. | Swenson et al. Algorithms for Molecular Biology 2011 6 11 http content 6 1 11 AMR ALGORITHMS FOR MOLECULAR BIOLOGY RESEARCH Open Access Listing all sorting reversals in quadratic time Krister M Swenson1 2 Ghada Badr3 4 and David Sankoff1 Abstract We describe an average-case O n2 algorithm to list all reversals on a signed permutation n that when applied to n produce a permutation that is closer to the identity. This algorithm is optimal in the sense that the time it takes to write the list is O n2 in the worst case. 1 Introduction In 1995 Hannenhalli and Pevzner 1 presented an algorithm to transform one genome into another in a minimum number of biologically plausible moves. They modeled a genome as a signed permutation and the move that they considered was the reversal the order of a substring of the permutation is reversed and the sign of each element in the substring is flipped. Since then many refinements and speed improvements have been developed 2-8 . In 2002 Siepel and Ajana et al. 9 10 showed how to list every parsimonious scenario of reversals each scenario being a proposed candidate for the true evolutionary history. Fundamental to their algorithms are O n3 techniques for finding all sorting reversals the reversals that at each step produce a permutation that is closer to the target permutation than the last. Ajana et al. 9 used these results to support the replication-directed reversal hypothesis. Lefebvre et al. 11 and Sankoff et al. 12 used similar methodology to gain insight into the distribution of reversal lengths between genomes. Algorithms that attempt to more succinctly represent all shortest-length scenarios 13 14 have also been developed. In this paper we show how to list all sorting reversals in O n2 time on average. This algorithm is optimal in the sense that there are O n2 safe cycle-splitting reversals in the worst case. We later give a family of permutations that have O n2 unsafe reversals. We implemented our algorithm in .

• Báo cáo khoa học
• Báo cáo sinh học hay
• cách trình bày báo cáo
• báo cáo sinh học
• công trình nghiên cứu sinh học
• tài liệu về sinh học