Reconstructing a history of recombinations from a set of sequences
作者： John Kececioglu , Dan Gusfield
DOI: 10.1016/S0166-218X(98)00074-2
关键词: Event (probability theory) 、 Edit distance 、 Mutation (genetic algorithm) 、 Chromosome (genetic algorithm) 、 Mathematics 、 Computational complexity theory 、 Algorithm 、 Sequence 、 Time complexity 、 Phylogenetic tree
摘要: Abstract One of the classic problems in computational biology is reconstruction evolutionary history. A recent trend area to increase explanatory power models that are considered by incorporating higher-order events more accurately reflect mechanisms mutation at level chromosome. We take a step this direction considering problem reconstructing an history for set genetic sequences have evolved recombination. Recombination non-tree-like event produces child sequence crossing two parent sequences. present polynomial-time algorithms parsimonious such several recombination when all sequences, including those ancestors, input. also show these appear be near limit what can solved polynomial time, natural generalizations NP-complete.
elsevier.com
sci-hub.se 参考文章(45)
Sampath K. Kannan, Eugene. W. Myers, An Algorithm for Locating Non-Overlapping Regions of Maximum Alignment Score combinatorial pattern matching. pp. 74- 86 ,(1993) , 10.1007/BFB0029798
Gad M. Landau, Jeanette P. Schmidt, An Algorithm for Approximate Tandem Repeats combinatorial pattern matching. pp. 120- 133 ,(1993) , 10.1007/BFB0029801
M. Farach, S. Kannan, T. Warnow, A robust model for finding optimal evolutionary trees Algorithmica. ,vol. 13, pp. 155- 179 ,(1995) , 10.1007/BF01188585
Robert A. Wagner, On the complexity of the Extended String-to-String Correction Problem Proceedings of seventh annual ACM symposium on Theory of computing - STOC '75. pp. 218- 223 ,(1975) , 10.1145/800116.803771
Norman Kaplan, Richard R. Hudson, The use of sample genealogies for studying a selectively neutral m-loci model with recombination. Theoretical Population Biology. ,vol. 28, pp. 382- 396 ,(1985) , 10.1016/0040-5809(85)90036-X
Dan Gusfield, John Kececioglu, Reconstructing a history of recombinations from a set of sequences symposium on discrete algorithms. pp. 471- 480 ,(1994) , 10.5555/314464.314626
Michael R. Garey, David S. Johnson, Computers and Intractability: A Guide to the Theory of NP-Completeness ,(1979)
Richard R. Hudson, Properties of a neutral allele model with intragenic recombination Theoretical Population Biology. ,vol. 23, pp. 183- 201 ,(1983) , 10.1016/0040-5809(83)90013-8
Vineet Bafna, Pavel A. Pevzner, Sorting by Transpositions SIAM Journal on Discrete Mathematics. ,vol. 11, pp. 224- 240 ,(1998) , 10.1137/S089548019528280X
John D. Kececioglu, R. Ravi, Of mice and men: algorithms for evolutionary distances between genomes with translocation symposium on discrete algorithms. pp. 604- 613 ,(1995) , 10.5555/313651.313825