Notices
Results 1 to 13 of 13
Like Tree3Likes
  • 2 Post By tridimity
  • 1 Post By John Galt

Thread: evolutionary computations in sequence alignment

  1. #1 evolutionary computations in sequence alignment 
    Forum Freshman
    Join Date
    Jan 2012
    Posts
    16
    hi,
    I badly need to know which algorithm of evolutionary computations such as ACO and PSO best with sequence alignment, especially if have large database of sequences?

    I do appreciate any advice.
    Also, if anyone have papers on these algorithms with sequence alignment ,please provide it for me.

    Many thanks


    Reply With Quote  
     

  2.  
     

  3. #2  
    Forum Bachelors Degree
    Join Date
    Jul 2008
    Posts
    420
    Hi Huda,

    I'm out of my depth here, nevertheless a couple of papers (1,2) on PSO and ACO sequence alignment algorithms point out the following:

    PSO (1)
    • in the adapted PSO algorithm, a particle reperesents a sequence alignment
    • the general algorithm is: 1. generate a set of initial particles 2. determine the leader particle gbest 3. repeat until the termination criterion is met a. measure the distance between gbest and every particle b. move every particle towards gbest c. determine the leader particle
    • the overall concept, is to have a set of particles that are randomly sparse over a search space, be progressively moved to regions which will provide better solutions to the problem. This continues until the swarm finds a solution that it cannot improve anymore.
    • apparently superior to ClustalX
    ACO (2)
    • aims to enhance sequence alignment performance by incorporating local search, ant colony optimisation (ACO)
    • the process involves taking an initial population > evaluate fitness > satisfy termination condition then end OR dissatisfy termination condition > this population undergoes 'mutation'/'sexual reproduction'/'clone' (I don't understand this part..) > enter a selection pool > evaluate fitness and selection > new population > ant colony optimisation > next generation > satisfy termination condition then ends OR dissatisfy termination condition (and so on).
    • the authors claim that GA-ACO out-performs other existing algorithms
    For further details and the underlying mathematics, please refer to the cited papers. For everyday purposes, I would recommend DNA Dynamo sequence analysis software.

    Best wishes,

    Tridimity


    Ref.

    1) Xu & Chen (2009) A Method for Multiple Sequence Alignment Based on Particle Swarm Optimization. http://cilab.ujn.edu.cn/paper/A%20Method%20for%20Multiple%20Sequence%20Alignment .pdf

    2) L
    ee et al (2008) Genetic algorithm with ant colony optimisation (GA-ACO) for multiple sequence alignment. Applied Soft Computing Genetic algorithm with ant colony optimization (GA-ACO) for multiple sequence alignment 10.1016/j.asoc.2006.10.012 : Applied Soft Computing | ScienceDirect.com


    John Galt and huda like this.
    Reply With Quote  
     

  4. #3  
    Universal Mind John Galt's Avatar
    Join Date
    Jul 2005
    Posts
    14,168
    I have no idea what you are talking about, but I can recognise the thought and effort that went into providing a technical focused reply and believe it should be rewarded.
    Reply With Quote  
     

  5. #4  
    Forum Freshman
    Join Date
    Jan 2012
    Posts
    16
    thanks for these information, i hope u see my new thread sequence alignment and reply to me
    Reply With Quote  
     

  6. #5  
    Forum Freshman
    Join Date
    Jan 2012
    Posts
    16
    Quote Originally Posted by John Galt View Post
    I have no idea what you are talking about, but I can recognise the thought and effort that went into providing a technical focused reply and believe it should be rewarded.
    what is the type of reward?
    Reply With Quote  
     

  7. #6  
    Universal Mind John Galt's Avatar
    Join Date
    Jul 2005
    Posts
    14,168
    I rewarded him with a "Like" which you can see at the bottom of his post.
    huda likes this.
    Reply With Quote  
     

  8. #7  
    Forum Freshman
    Join Date
    Jan 2012
    Posts
    16
    Quote Originally Posted by John Galt View Post
    I rewarded him with a "Like" which you can see at the bottom of his post.
    thanks for this note so , i will rewarded u too such tridimity I almost don't care with these things, but I promise u to consider it in future
    Reply With Quote  
     

  9. #8  
    Forum Bachelors Degree
    Join Date
    Jul 2008
    Posts
    420
    Quote Originally Posted by John Galt View Post
    I rewarded him with a "Like" which you can see at the bottom of his post.
    I'm female, but thanks.
    Reply With Quote  
     

  10. #9  
    Universal Mind John Galt's Avatar
    Join Date
    Jul 2005
    Posts
    14,168
    Quote Originally Posted by tridimity View Post
    Quote Originally Posted by John Galt View Post
    I rewarded him with a "Like" which you can see at the bottom of his post.
    I'm female, but thanks.
    My apologies. You see, I can't even distinguish between X and Y chromosomes.
    Reply With Quote  
     

  11. #10  
    Forum Bachelors Degree
    Join Date
    Jul 2008
    Posts
    420
    Quote Originally Posted by John Galt View Post
    Quote Originally Posted by tridimity View Post
    Quote Originally Posted by John Galt View Post
    I rewarded him with a "Like" which you can see at the bottom of his post.
    I'm female, but thanks.
    My apologies. You see, I can't even distinguish between X and Y chromosomes.


    Tridmity
    Reply With Quote  
     

  12. #11  
    Forum Freshman
    Join Date
    Jan 2012
    Posts
    16
    Quote Originally Posted by tridimity View Post
    Quote Originally Posted by John Galt View Post
    I rewarded him with a "Like" which you can see at the bottom of his post.
    I'm female, but thanks.
    hi Tridmity,
    I used PSO algorithm with sequence alignment.
    I built the algorithm , but face some issues.

    as u know in dynamic programming we get the alignment matrix in case of global alignment as follow:
    [F(i,j) I(i,j)] = max([ F(i-1,j)+g F(i-1,j-1)+w(i,j) F(i,j-1)+g]);

    where F is alignment matrix and I is used to trace back for path.
    In PSO algorithm , the matrix alignment is generated randomly with conditions as initial then update it .
    the prolem now is how can trace back the path in this matrix:

    0.9022 0.8679 0.5648 0.5864 0.9341 0.6726 0.8110 0.8444
    0.4721 0.5310 0.9709 0.0988 0.6155 1.0870 0.6434 0.6384
    0.9748 0.3597 -0.3150 0.1227 1.0207 0.5794 0.2709 1.0193
    0.4295 0.7370 0.1699 0.1496 0.7649 0.5265 0.7317 0.6369
    0.8445 0.4816 0.2194 0.7452 0.6399 0.8799 0.0917 0.0186
    0.4357 0.9152 0.4468 -1.3274 0.8953 0.2502 0.6873 0.1327
    0.8877 0.8442 0.8221 0.2083 1.2358 0.5469 0.7257 0.9473
    0.8291 0.1836 0.9065 0.5435 1.0858 0.7048 0.8013 0.5318
    0.4144 0.9465 0.8674 0.1621 0.0006 0.3264 0.8714 0.9277
    0.2372 1.0869 0.3497 0.0604 0.9503 0.9280 1.0786 1.0756


    any advice , informtion may help.
    thanks in advnce
    Reply With Quote  
     

  13. #12  
    Forum Bachelors Degree
    Join Date
    Jul 2008
    Posts
    420
    Quote Originally Posted by huda View Post
    Quote Originally Posted by tridimity View Post
    Quote Originally Posted by John Galt View Post
    I rewarded him with a "Like" which you can see at the bottom of his post.
    I'm female, but thanks.
    hi Tridmity,
    I used PSO algorithm with sequence alignment.
    I built the algorithm , but face some issues.

    as u know in dynamic programming we get the alignment matrix in case of global alignment as follow:
    [F(i,j) I(i,j)] = max([ F(i-1,j)+g F(i-1,j-1)+w(i,j) F(i,j-1)+g]);

    where F is alignment matrix and I is used to trace back for path.
    In PSO algorithm , the matrix alignment is generated randomly with conditions as initial then update it .
    the prolem now is how can trace back the path in this matrix:

    0.9022 0.8679 0.5648 0.5864 0.9341 0.6726 0.8110 0.8444
    0.4721 0.5310 0.9709 0.0988 0.6155 1.0870 0.6434 0.6384
    0.9748 0.3597 -0.3150 0.1227 1.0207 0.5794 0.2709 1.0193
    0.4295 0.7370 0.1699 0.1496 0.7649 0.5265 0.7317 0.6369
    0.8445 0.4816 0.2194 0.7452 0.6399 0.8799 0.0917 0.0186
    0.4357 0.9152 0.4468 -1.3274 0.8953 0.2502 0.6873 0.1327
    0.8877 0.8442 0.8221 0.2083 1.2358 0.5469 0.7257 0.9473
    0.8291 0.1836 0.9065 0.5435 1.0858 0.7048 0.8013 0.5318
    0.4144 0.9465 0.8674 0.1621 0.0006 0.3264 0.8714 0.9277
    0.2372 1.0869 0.3497 0.0604 0.9503 0.9280 1.0786 1.0756


    any advice , informtion may help.
    thanks in advnce
    Hi Huda,

    I don't understand what is 'I' or how to trace back for the path.

    For global alignment, the following dynamic programming can be used:

    Needleman-Wunsch Algorithm

    Initialization: F(0, j) = 6j d, F(i, 0) = 6i d
     Recurrence: F(i, j) = Max{ F(i 61, j) – d, F(i, j61) – d, F(i61, j61) + S(Xi,Yj)}

    Banded dynamic programming

    Initialization: F(0, j) = 6j d, F(i, 0) = 6i d such that i, j ≤ k(n)
    Recurrence: F(i, j) = Max{ F(i 61, j) – d, F(i, j61) – d, F(i61, j61) + S(Xi,Yj)} if |i – j| < k(n)

    Please could you clarify what 'I' is?

    Thanks,

    Tri~






    Reply With Quote  
     

  14. #13  
    Forum Professor Zwirko's Avatar
    Join Date
    Sep 2008
    Location
    55 N, 3 W
    Posts
    1,085
    This link of any use?: Global Alignment: Needleman-Wunsch.


    Reply With Quote  
     

Similar Threads

  1. 2012 Alignment of Sun to the Galaxy center
    By dedo in forum Astronomy & Cosmology
    Replies: 37
    Last Post: December 3rd, 2010, 05:28 AM
  2. Number Sequence
    By Heinsbergrelatz in forum Mathematics
    Replies: 7
    Last Post: January 18th, 2010, 12:11 AM
  3. protein structure alignment in 3D
    By mitxyz in forum Chemistry
    Replies: 0
    Last Post: November 21st, 2008, 11:16 PM
  4. Planatary alignment
    By MacGyver1968 in forum Astronomy & Cosmology
    Replies: 2
    Last Post: May 21st, 2007, 02:38 AM
  5. Fibonacci Sequence
    By DesertFoxx in forum Mathematics
    Replies: 7
    Last Post: June 12th, 2006, 02:39 AM
Tags for this Thread
aco, pso

View Tag Cloud

Bookmarks
Bookmarks
Posting Permissions
  • You may not post new threads
  • You may not post replies
  • You may not post attachments
  • You may not edit your posts
  •