DFS-generated pathways in GA crossover for protein structure prediction

Md Tamjidul Hoque, Madhusudan Chetty, Andrew Lewis, Abdul Sattar, Vicky Avery

    Research output: Contribution to journalArticleResearchpeer-review

    13 Citations (Scopus)


    Genetic algorithms (GAs), as nondeterministic conformational search techniques, are promising for solving protein structure prediction (PSP) problems. The crossover operator of a GA can underpin the formation of potential conformations by exchanging and sharing potential sub-conformations. However, as the optimum PSP conformation is usually compact, the crossover operation may result in many invalid conformations (by having non-self-avoiding walks). Although a crossover-based converging conformation suffers from limited pathways, combining it with depth-first search (DFS) can partially reveal potential pathways and make an invalid crossover valid and successful. Random conformations are frequently applied for maintaining diversity as well as for initialization in many GA applications. The random-move-only-based conformation generator has exponential time complexity in generating random conformations, whereas the DFS-based random conformation generator has linear time complexity and performs relatively faster. We have performed extensive experiments using popular 2D, as well as useful 3D, models to justify our hypothesis empirically.
    Original languageEnglish
    Pages (from-to)2308 - 2316
    Number of pages9
    Issue number13-15
    Publication statusPublished - 2010

    Cite this