Toward efficient multiple molecular sequence alignment: A system of genetic algorithm and dynamic programming

被引:19
作者
Zhang, C
Wong, AKC
机构
[1] Department of Systems Design Engineering, University of Waterloo, Waterloo
来源
IEEE TRANSACTIONS ON SYSTEMS MAN AND CYBERNETICS PART B-CYBERNETICS | 1997年 / 27卷 / 06期
关键词
biomolecular sequence alignment; dynamic programming; genetic algorithm; multiple sequence alignment;
D O I
10.1109/3477.650054
中图分类号
TP [自动化技术、计算机技术];
学科分类号
0812 ;
摘要
Multiple biomolecular sequence alignment is among the most important and challenging tasks in computational biology, It is characterized by great complexity in processing time. In this paper, a multiple-sequence alignment system is reported which combines the techniques of genetic algorithms and pairwise dynamic programming, Genetic algorithms are stochastic approaches for efficient and robust search, By converting biomolecular sequence alignment into a problem of searching for an optimal or a near-optimal point in a solution space, a genetic algorithm is used to find match blocks very efficiently. A pairwise dynamic programming is then applied, to the subsequences between the match blocks, Combining the strengths of the two methods, the system achieves high efficiency and high alignment quality, In this paper, the system is described in detail, The system's performance is analyzed and the experimental results are presented.
引用
收藏
页码:918 / 932
页数:15
相关论文
共 38 条
  • [1] ANKENBRANDT CA, 1991, FDN GENETIC ALGORITH, P53
  • [2] Buckles BP, 1990, P TOOLS ARTIFICIAL I
  • [3] A SURVEY OF MULTIPLE SEQUENCE COMPARISON METHODS
    CHAN, SC
    WONG, AKC
    CHIU, DKY
    [J]. BULLETIN OF MATHEMATICAL BIOLOGY, 1992, 54 (04) : 563 - 598
  • [4] CHAN SC, 1990, THESIS U WATERLOO WA
  • [5] POTENTIAL OF GENETIC ALGORITHMS IN PROTEIN FOLDING AND PROTEIN ENGINEERING SIMULATIONS
    DANDEKAR, T
    ARGOS, P
    [J]. PROTEIN ENGINEERING, 1992, 5 (07): : 637 - 645
  • [6] De Jong K., 1988, Machine Learning, V3, P121, DOI 10.1023/A:1022606120092
  • [7] ALIGNING AMINO-ACID SEQUENCES - COMPARISON OF COMMONLY USED METHODS
    FENG, DF
    JOHNSON, MS
    DOOLITTLE, RF
    [J]. JOURNAL OF MOLECULAR EVOLUTION, 1985, 21 (02) : 112 - 125
  • [8] PROGRESSIVE SEQUENCE ALIGNMENT AS A PREREQUISITE TO CORRECT PHYLOGENETIC TREES
    FENG, DF
    DOOLITTLE, RF
    [J]. JOURNAL OF MOLECULAR EVOLUTION, 1987, 25 (04) : 351 - 360
  • [9] Goldberg David E, 1987, Genetic algorithms and simulated annealing, P74
  • [10] Goldberg DE, 1989, GENETIC ALGORITHMS S