Seqanswers Leaderboard Ad

Collapse

Announcement

Collapse
No announcement yet.
X
 
  • Filter
  • Time
  • Show
Clear All
new posts

  • Comparison of alignment algorithms

    Hi all,
    I was wondering how the different algorithms for optimal alignments (NW, SW etc.) compare to each other in terms of runtime, since I've been told that NW and SW are very ineffective/slow, but Hirschberg and Gotoh only offer minor improvements (if any).
    So far I've found differing statements concerning complexity and runtime...

    My main focus lies on runtime, though memory requirements are of course to be considered as well if there are very great differences.
    I hope that somebody can detangle the whole subject for me, especially in terms of linear and affine gap costs.
    Oh and please don't tell me to use public available aligners like bowtie or BWA instead (I already do that btw), because this is absolutely NOT helping with my project at university

    Thank you in advance and have a nice day

  • #2
    Ah, so this is for homework, so should we really be helping?

    Did you know that all these algorithms can be made to work in a linear amount of memory (think Frontier search)? Their time complexities are well described their respective papers, so I am not sure how they are differing.

    Linear vs. Affine really comes down to finding longer gaps, and what are the relative scoring penalties (gap open/extend vs. mismatch/match).

    Comment


    • #3
      Thehe, since the goal is to implement a fast aligner, I was hoping you could give me a push in the right direction in terms of which algorithm to chose
      For example, I read that Hirschberg algorithm is a little slower than NW but way more efficient concerning memory, but this is just slightly indicated by the complexity mentioned (if it is mentioned at all, I'm not sure right now).
      That is why I would like to have a ranking or a table that tells me which of the algorithms is the fastest/best in terms of runtime and memory consumption (I think this might be handy for other people as well).
      I already tried to find something like that, but I didn't succeed so far (will continue searching though).

      Regards

      Comment


      • #4
        Originally posted by rboettcher View Post
        Hi all,
        Oh and please don't tell me to use public available aligners like bowtie or BWA instead (I already do that btw), because this is absolutely NOT helping with my project at university
        Sorry for not having an answer for your question. But your phrase called my attention, why is this so?

        Comment


        • #5
          It does not help because I was told to implement a pairwise sequence alignment which is time dependent and very accurate
          I tried to get some inspiration from the commonly used software, but until now it is a little to advanced for me...
          Moreover it has to be finished soon, that is why I'm searching for help.
          We're also using common aligners for getting used to the handling, still I'm obliged to implement some algorithm using a dynamic programming approach for reasons of understanding the whole process (and as programming exercise).
          If you think it's a waste of time feel free to contact my professor

          Regards
          Last edited by rboettcher; 04-06-2011, 12:13 AM.

          Comment


          • #6
            The hirschberg (or Gotoh's?) technique, if I recall, pretty much involves in recursively breaking the alignment down into smaller bits. However to find an appropriate point on the alignment matrix to split at it has to run the alignment through anyway, albeit without storing data, so it essentially does double the work in order to use far less memory. I may be wrong on that though as it's been a long time!

            I'd advise checking some of the earlier linear space alignment algorithms from Miller and Myers. They're pretty hard to follow due to excessive use of single letter variables, but they're a goof starting point for full local and global alignment calculations. See http://bioinformatics.oxfordjournals...t/4/1/11.short. They later did a variant that uses a band to avoid the full N^2 complexity, and later still some block stiching version.

            Modern techniques tend to use hashing more though - looking for exact matching "words" of sequence and then either stitching these together to produce an actual alignment or using the location of the words to control a band through the alignment matrix.

            Comment

            Latest Articles

            Collapse

            • seqadmin
              Exploring the Dynamics of the Tumor Microenvironment
              by seqadmin




              The complexity of cancer is clearly demonstrated in the diverse ecosystem of the tumor microenvironment (TME). The TME is made up of numerous cell types and its development begins with the changes that happen during oncogenesis. “Genomic mutations, copy number changes, epigenetic alterations, and alternative gene expression occur to varying degrees within the affected tumor cells,” explained Andrea O’Hara, Ph.D., Strategic Technical Specialist at Azenta. “As...
              07-08-2024, 03:19 PM
            • seqadmin
              Exploring Human Diversity Through Large-Scale Omics
              by seqadmin


              In 2003, researchers from the Human Genome Project (HGP) announced the most comprehensive genome to date1. Although the genome wasn’t fully completed until nearly 20 years later2, numerous large-scale projects, such as the International HapMap Project and 1000 Genomes Project, continued the HGP's work, capturing extensive variation and genomic diversity within humans. Recently, newer initiatives have significantly increased in scale and expanded beyond genomics, offering a more detailed...
              06-25-2024, 06:43 AM

            ad_right_rmr

            Collapse

            News

            Collapse

            Topics Statistics Last Post
            Started by seqadmin, 07-19-2024, 07:20 AM
            0 responses
            40 views
            0 likes
            Last Post seqadmin  
            Started by seqadmin, 07-16-2024, 05:49 AM
            0 responses
            52 views
            0 likes
            Last Post seqadmin  
            Started by seqadmin, 07-15-2024, 06:53 AM
            0 responses
            64 views
            0 likes
            Last Post seqadmin  
            Started by seqadmin, 07-10-2024, 07:30 AM
            0 responses
            43 views
            0 likes
            Last Post seqadmin  
            Working...
            X