异构机群系统中序列比对并行算法进展
|
摘要
简要介绍生物序列比对问题,生物序列比对分为双序列比对和多序列比对两大类,介绍了双序列比对并行算法和多序列比对并行算法的研究现状,并分析它们的主要设计思想及其性能。最后,对异构机群计算环境下序列比对近似并行算法的研究进行简要讨论。
引文
[1]崔鑫.异构机群系统上序列比对并行处理研究.南宁:广西大学,2008
[2]钟诚,宋彬.生物序列比对算法分析与比较.广西大学学报(自然科学版),2004,29(3):214-221
[3]冯百龙.双序列比对Needleman-Wunsch算法的分布式并行化研究.内蒙古:内蒙古农业大学,2015
[4]Stjepan Rajko,Srinivas Alum.Space and Time Optimal Parallel Sequence Alignments.IEEE Transactions on parallel and distributed systems,2004,P1070-1081
[5]S A luru,N Futamura,K Mehrotra.Parallel biological sequence comparison using prefix computations.Journal of Parallel and Distributed Computing,2003,63(3):264-272
[6]崔鑫,钟诚,陆向艳.异构机群系统上双序列全局比对并行算法.计算机工程与应用,2009,45(8):58-61
[7]Bonizzoni P,Della Vedova G.The complexity of multiple sequence alignment with SP-score that is metric.Theoretical Computer Science,2001,259(122):63-79
[8]WAN G L,J IAN G T.On the complexity of multiple sequence alignment.J Comput.Biol.,1994,1:337-348
[9]J IANG T,Lawler E L,WAN G L.Aligning sequences via anevolutional tree:complexity and approximation.Proc.26th ACM Symp.On Theory of Computing[C].New York:ACM Press,1994.760-769
[10]L I M,MA B,WANGL.Finding similar regions in many strings.Proc31th ACM Symp.On Theory of Computing[C],New York:ACM Press,1999,473-482
[11]Gusfield D.Efficient methods for multiple sequence alignment with guaranteed error bounds.BuIIetin of Mathematical Biology,1993,55:141-154
[12]Bafna V,Lawer E,Pevzner P.Approximation algorithms for multiple sequence alignment.Theoretical Computer Science,1997,182:233-244
[13]MA B,WANG L,LI M.Near optimal multiple alignment within a band in polynomial time.Journal of Computer and System Sciences,2007,73(6):997-1011
[14]M Ishikawa,M Ho sh ida,M H iro sawa,etal.Multiple sequence alignment by parallel simulated annealing.Comput Appl Bio Sici,1992:267-273
[15]M P Berger,P J Munson.A Novel randomized literative strategy for aligning multiple protein sequences,Comput App I B io sci,1991,479-484
[16]GOHOTO.Significant improvement in accuracy of multiple protein sequence alignment by iterative refinement as assessed by referenceto structural alignment.J.Mol.Biol.1996,264:823-838
[17]EDGAR R C.Muscle:multiple sequence alignment with high accuracy and high throughput.Nucleic Acids Res,2004,32:1792-1797
[18]Chunxi Chen,Bertil Schmidt.An adaptive grid implementation of DNA sequence alignment.Future Generation Computer Systems,2005,21:988-1003
[19]A.Legrand,A.Su,F.Vivien.Minimizing the stretch when scheduling flows of biological requests.Journal of Scheduling,2008,11(5):381-404
[20]Nguyen H D,Yoshihara I,Yamamori K,etal.Aligning Multiple Protein Sequences by Parallel Hybrid Genetic Algorithm.Genome Informatics,2002,13:123-132
[21]宋彬,陈国良,鄢超,沈一飞.多序列比对问题的并行近似算法.中国科技大学学报,2005,35(5):656-664
[2]钟诚,宋彬.生物序列比对算法分析与比较.广西大学学报(自然科学版),2004,29(3):214-221
[3]冯百龙.双序列比对Needleman-Wunsch算法的分布式并行化研究.内蒙古:内蒙古农业大学,2015
[4]Stjepan Rajko,Srinivas Alum.Space and Time Optimal Parallel Sequence Alignments.IEEE Transactions on parallel and distributed systems,2004,P1070-1081
[5]S A luru,N Futamura,K Mehrotra.Parallel biological sequence comparison using prefix computations.Journal of Parallel and Distributed Computing,2003,63(3):264-272
[6]崔鑫,钟诚,陆向艳.异构机群系统上双序列全局比对并行算法.计算机工程与应用,2009,45(8):58-61
[7]Bonizzoni P,Della Vedova G.The complexity of multiple sequence alignment with SP-score that is metric.Theoretical Computer Science,2001,259(122):63-79
[8]WAN G L,J IAN G T.On the complexity of multiple sequence alignment.J Comput.Biol.,1994,1:337-348
[9]J IANG T,Lawler E L,WAN G L.Aligning sequences via anevolutional tree:complexity and approximation.Proc.26th ACM Symp.On Theory of Computing[C].New York:ACM Press,1994.760-769
[10]L I M,MA B,WANGL.Finding similar regions in many strings.Proc31th ACM Symp.On Theory of Computing[C],New York:ACM Press,1999,473-482
[11]Gusfield D.Efficient methods for multiple sequence alignment with guaranteed error bounds.BuIIetin of Mathematical Biology,1993,55:141-154
[12]Bafna V,Lawer E,Pevzner P.Approximation algorithms for multiple sequence alignment.Theoretical Computer Science,1997,182:233-244
[13]MA B,WANG L,LI M.Near optimal multiple alignment within a band in polynomial time.Journal of Computer and System Sciences,2007,73(6):997-1011
[14]M Ishikawa,M Ho sh ida,M H iro sawa,etal.Multiple sequence alignment by parallel simulated annealing.Comput Appl Bio Sici,1992:267-273
[15]M P Berger,P J Munson.A Novel randomized literative strategy for aligning multiple protein sequences,Comput App I B io sci,1991,479-484
[16]GOHOTO.Significant improvement in accuracy of multiple protein sequence alignment by iterative refinement as assessed by referenceto structural alignment.J.Mol.Biol.1996,264:823-838
[17]EDGAR R C.Muscle:multiple sequence alignment with high accuracy and high throughput.Nucleic Acids Res,2004,32:1792-1797
[18]Chunxi Chen,Bertil Schmidt.An adaptive grid implementation of DNA sequence alignment.Future Generation Computer Systems,2005,21:988-1003
[19]A.Legrand,A.Su,F.Vivien.Minimizing the stretch when scheduling flows of biological requests.Journal of Scheduling,2008,11(5):381-404
[20]Nguyen H D,Yoshihara I,Yamamori K,etal.Aligning Multiple Protein Sequences by Parallel Hybrid Genetic Algorithm.Genome Informatics,2002,13:123-132
[21]宋彬,陈国良,鄢超,沈一飞.多序列比对问题的并行近似算法.中国科技大学学报,2005,35(5):656-664