• <ins id="pjuwb"></ins>
    <blockquote id="pjuwb"><pre id="pjuwb"></pre></blockquote>
    <noscript id="pjuwb"></noscript>
          <sup id="pjuwb"><pre id="pjuwb"></pre></sup>
            <dd id="pjuwb"></dd>
            <abbr id="pjuwb"></abbr>
            隨筆 - 87  文章 - 279  trackbacks - 0
            <2006年9月>
            272829303112
            3456789
            10111213141516
            17181920212223
            24252627282930
            1234567

            潛心看書研究!

            常用鏈接

            留言簿(19)

            隨筆分類(81)

            文章分類(89)

            相冊

            ACM OJ

            My friends

            搜索

            •  

            積分與排名

            • 積分 - 217919
            • 排名 - 117

            最新評論

            閱讀排行榜

            評論排行榜

            Human Gene Functions
            Time Limit:1000MS? Memory Limit:10000K
            Total Submit:866 Accepted:507

            Description
            It is well known that a human gene can be considered as a sequence, consisting of four nucleotides, which are simply denoted by four letters, A, C, G, and T. Biologists have been interested in identifying human genes and determining their functions, because these can be used to diagnose human diseases and to design new drugs for them.

            A human gene can be identified through a series of time-consuming biological experiments, often with the help of computer programs. Once a sequence of a gene is obtained, the next job is to determine its function.
            One of the methods for biologists to use in determining the function of a new gene sequence that they have just identified is to search a database with the new gene as a query. The database to be searched stores many gene sequences and their functions – many researchers have been submitting their genes and functions to the database and the database is freely accessible through the Internet.

            A database search will return a list of gene sequences from the database that are similar to the query gene.
            Biologists assume that sequence similarity often implies functional similarity. So, the function of the new gene might be one of the functions that the genes from the list have. To exactly determine which one is the right one another series of biological experiments will be needed.

            Your job is to make a program that compares two genes and determines their similarity as explained below. Your program may be used as a part of the database search if you can provide an efficient one.
            Given two genes AGTGATG and GTTAG, how similar are they? One of the methods to measure the similarity
            of two genes is called alignment. In an alignment, spaces are inserted, if necessary, in appropriate positions of
            the genes to make them equally long and score the resulting genes according to a scoring matrix.

            For example, one space is inserted into AGTGATG to result in AGTGAT-G, and three spaces are inserted into GTTAG to result in –GT--TAG. A space is denoted by a minus sign (-). The two genes are now of equal
            length. These two strings are aligned:

            AGTGAT-G
            -GT--TAG

            In this alignment, there are four matches, namely, G in the second position, T in the third, T in the sixth, and G in the eighth. Each pair of aligned characters is assigned a score according to the following scoring matrix.


            denotes that a space-space match is not allowed. The score of the alignment above is (-3)+5+5+(-2)+(-3)+5+(-3)+5=9.

            Of course, many other alignments are possible. One is shown below (a different number of spaces are inserted into different positions):

            AGTGATG
            -GTTA-G

            This alignment gives a score of (-3)+5+5+(-2)+5+(-1) +5=14. So, this one is better than the previous one. As a matter of fact, this one is optimal since no other alignment can have a higher score. So, it is said that the
            similarity of the two genes is 14.

            Input
            The input consists of T test cases. The number of test cases ) (T is given in the first line of the input file. Each test case consists of two lines: each line contains an integer, the length of a gene, followed by a gene sequence. The length of each gene sequence is at least one and does not exceed 100.

            Output
            The output should print the similarity of each test case, one per line.

            Sample Input

            2 
            7 AGTGATG 
            5 GTTAG 
            7 AGCTATT 
            9 AGCTTTAAA 

            Sample Output

            14
            21 

            Source
            Taejon 2001

            ???????#include? < iostream >
            using ? namespace ?std;

            int ?map[ 100 ][ 100 ];
            int ?initMap()
            {
            ????map[
            ' A ' ][ ' C ' ]? = ?map[ ' C ' ][ ' A ' ]? = ? - 1 ;
            ????map[
            ' A ' ][ ' G ' ]? = ?map[ ' G ' ][ ' A ' ]? = ? - 2 ;
            ????map[
            ' A ' ][ ' T ' ]? = ?map[ ' T ' ][ ' A ' ]? = ? - 1 ;
            ????map[
            ' A ' ][ ' - ' ]? = ?map[ ' - ' ][ ' A ' ]? = ? - 3 ;

            ????map[
            ' C ' ][ ' G ' ]? = ?map[ ' G ' ][ ' C ' ]? = ? - 3 ;
            ????map[
            ' C ' ][ ' T ' ]? = ?map[ ' T ' ][ ' C ' ]? = ? - 2 ;
            ????map[
            ' C ' ][ ' - ' ]? = ?map[ ' - ' ][ ' C ' ]? = ? - 4 ;

            ????map[
            ' G ' ][ ' T ' ]? = ?map[ ' T ' ][ ' G ' ]? = ? - 2 ;
            ????map[
            ' G ' ][ ' - ' ]? = ?map[ ' - ' ][ ' G ' ]? = ? - 2 ;

            ????map[
            ' T ' ][ ' - ' ]? = ?map[ ' - ' ][ ' T ' ]? = ? - 1 ;

            ????map[
            ' A ' ][ ' A ' ]? = ?map[ ' T ' ][ ' T ' ]? = ?map[ ' G ' ][ ' G ' ]? = ?map[ ' C ' ][ ' C ' ]? = ? 5 ;
            ????map[
            ' - ' ][ ' - ' ]? = ? - 128 ;
            ????
            return ? 0 ;
            }


            int ?solve()
            {
            ????
            int ?i,?j;
            ????
            char ?s1[ 105 ],?s2[ 105 ];
            ????
            int ?dp[ 105 ][ 105 ];
            ????
            int ?l1,?l2;
            ????cin?
            >> ?l1? >> ?s1? >> ?l2? >> ?s2;
            ????dp[
            0 ][ 0 ]? = ? 0 ;
            ????
            for ?(i = 1 ;?i <= l1;?i ++ )
            ????????dp[i][
            0 ]? = ?dp[i - 1 ][ 0 ]? + ?map[s1[i - 1 ]][ ' - ' ];
            ????
            for ?(i = 1 ;?i <= l2;?i ++ )
            ????????dp[
            0 ][i]? = ?dp[ 0 ][i - 1 ]? + ?map[ ' - ' ][s2[i - 1 ]];

            ????
            for ?(i = 1 ;?i <= l1;?i ++ )
            ????????
            for ?(j = 1 ;?j <= l2;?j ++ )
            ????????
            {
            ????????????dp[i][j]?
            = ?dp[i - 1 ][j - 1 ]? + ?map[s1[i - 1 ]][s2[j - 1 ]];
            ????????????
            if ?(dp[i][j]? < ?dp[i][j - 1 ]? + ?map[ ' - ' ][s2[j - 1 ]])
            ????????????????dp[i][j]?
            = ?dp[i][j - 1 ]? + ?map[ ' - ' ][s2[j - 1 ]];
            ????????????
            if ?(dp[i][j]? < ?dp[i - 1 ][j]? + ?map[s1[i - 1 ]][ ' - ' ])
            ????????????????dp[i][j]?
            = ?dp[i - 1 ][j]? + ?map[s1[i - 1 ]][ ' - ' ];
            ????????}

            ????cout?
            << ?dp[l1][l2]? << ?endl;
            ????
            return ? 0 ;
            }

            int ?main()
            {
            ????initMap();
            ????
            int ?caseTime;

            ????cin?
            >> ?caseTime;
            ????
            while ?(caseTime -- ? != ? 0 )
            ????
            {
            ????????solve();
            ????}

            ????
            return ? 0 ;
            }
            posted on 2006-08-21 15:47 閱讀(617) 評論(0)  編輯 收藏 引用 所屬分類: ACM題目
            国产aⅴ激情无码久久| 精品久久久无码人妻中文字幕豆芽 | 久久久久久精品久久久久| 麻豆AV一区二区三区久久| 久久99毛片免费观看不卡| 久久久久久毛片免费看| 亚洲国产欧美国产综合久久| 日本一区精品久久久久影院| 久久99九九国产免费看小说| 久久精品国产亚洲av日韩| 青青久久精品国产免费看| 国产亚洲欧美精品久久久| 亚洲v国产v天堂a无码久久| 久久久精品人妻一区二区三区蜜桃| 久久国产精品一区| 久久精品毛片免费观看| 久久久久久久免费视频| 国产精品无码久久久久| 久久精品亚洲精品国产色婷| 欧美国产精品久久高清| 色综合久久精品中文字幕首页| 亚洲国产欧美国产综合久久| 亚洲国产成人乱码精品女人久久久不卡 | 国内精品九九久久久精品| 精品国产乱码久久久久软件| 日韩亚洲欧美久久久www综合网| 久久亚洲日韩精品一区二区三区| 思思久久99热免费精品6| 久久综合久久综合九色| 久久国产精品久久国产精品| 青草国产精品久久久久久| 亚洲欧美成人综合久久久| 精品伊人久久久| 区亚洲欧美一级久久精品亚洲精品成人网久久久久 | 狠狠人妻久久久久久综合蜜桃| 久久婷婷五月综合色奶水99啪| 久久亚洲精品无码aⅴ大香| 国产精品久久久久久五月尺| 亚洲国产日韩综合久久精品| 欧美精品九九99久久在观看| 亚洲欧洲精品成人久久曰影片|