Global Sequence Alignment

Global Sequence Alignment

And Scoring Maxrix

 

خلاصه :

          با توجه به کاربرد وسیع الگوریتم ها و برنامه ها در علم زیست شناسی ، ما نیز در اینجا سعی می کنیم بخشی از مسائل موجود را توسط الگوریتم کامپیوتری پیاده سازی و حل نماییم.
در این تکلیف برای تطبیق دو توالی ژنومی از ماتریس امتیاز دهی و الگوریتم DP استفاده کنیم و دو توالی را بر اساس جدول امتیاز چنان تطبیق دهیم که بیشترین امتیاز به دست آید.

توضیح :

          در ابتدا بیاید یه دور نگاه به مسئله داشته باشیم ، آیا بین دو توالی ژنومی ارتباط معنا داری وجود دارد ؟ آیا ممکن است از نظر تکاملی منشاء یکسانی داشته باشند ؟ یا ممکن است از نظر عملکرد زیستی مشابه یکدیگر باشند ؟
این سوالاتی است که در زمان برخورد با دو یا چند توالی به ذهن خطور می کند.

جواب این سوالات جواب اینکه چرا باید دو توالی ژنومی را با هم تطبیق دهیم ؟ را نیز در خود دارد.

اگر دو ژنوم دارای توالی یکسانی باشند رفتار مشابهی از خود نشان می دهند ، پس اگر ما بتوانیم یک توالی جدید که برای ما نا آشناست با یک توالی دیگر تطبیق دهیم می توانیم خواص آنرا حدس بزنیم و یا اینکه منشاء دو توالی را تشخیص دهیم و ...

همه ی اینا در گروی این است که ما بتوانیم این توالی ها که معمولاٌ بسیار طولانی هستند را با هم تطبیق دهیم و اینجاست که نیاز به الگوریتم های کامپیوتری به وضوح احساس می شود.

حل مسئله :

          ما در این تکلیف برای تطبیق دو توالی از روش تبیق سراسری و ماتریس امتیاز دهی کمک گرفته ایم ، البته روش های دیگری چون Semi Global alignment و Local alignment  و Dot Matrix  و غیره وجود دارد .

Mathlab codes :

%Global Sequece Alignment

    clc

    Lenx=length(xi);% take lenght of sequence x

    Leny=length(yi);% take lenght of sequence y

    x=nt2int(xi); % int value of seqence x

    y=nt2int(yi); % int value of seqence y

    matrix=zeros(Lenx+1,Leny+1,2); % Create scoring matrix

    % Start to fill Scoring matrix

    for i=1:Lenx

        matrix(i+1,1)=(i*gp);

    end

    for i=1:Leny

        matrix(1,i+1)=(i*gp);

    end

    for i=2:Lenx+1

        for j=2:Leny+1

            SMM=matrix(i-1,j-1,1)+w(x(i-1),y(j-1));

            SDE=matrix(i,j-1,1)+gp;

            SIN=matrix(i-1,j,1)+gp;

            [matrix(i,j,1) matrix(i,j,2)]=max([SMM SDE SIN]);

        end

    end

  

    i=Lenx+1;

    j=Leny+1;

    m=max(i,j)-1;

    %Find the Path in Scoring matrix

    %peparing the modified Sequences for printing

   

    for t=0:m-1

        if matrix(i,j,2)==1

            seq(1,m-t)=x(i-1);

            seq(2,m-t)=y(j-1);

            i=i-1;

            j=j-1;

          

           

        elseif matrix(i,j,2)==2

            seq(1,m-t)=40;

            seq(2,m-t)=y(j-1);

            j=j-1;

           

        elseif matrix(i,j,2)==3

            seq(1,m-t)=x(i-1);

            seq(2,m-t)=40;

            i=i-1;

           

        end

    end

    Score=matrix(Lenx+1,Leny+1,1)            % Show th Score of alignment

    sequence=int2nt(seq,'unknown','-') % Show the modified sequences

نتیجه گیری :

          با توجه به تعدادی از نتایج بدست آمده می توان دید که برنامه نویسی پویا نتایج قابل قبولی را برای ما به ارمغان می آورد.
در هر حال روش های دیگری نیز وجود دارد که بعضی از نقیصه های تبطیق سراری را رفع نموده ونتایج کارآمد تری از خود نشان داده اند.
در مجموع می توان تطبیق سراسری را یکی از روش های تطبیق توالی ها دانست.