• <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
            <2025年7月>
            293012345
            6789101112
            13141516171819
            20212223242526
            272829303112
            3456789

            潛心看書研究!

            常用鏈接

            留言簿(19)

            隨筆分類(81)

            文章分類(89)

            相冊

            ACM OJ

            My friends

            搜索

            •  

            積分與排名

            • 積分 - 217948
            • 排名 - 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題目
            亚洲一本综合久久| 国产精品亚洲美女久久久| 久久播电影网| 久久亚洲国产成人影院网站| 欧美国产成人久久精品| 熟妇人妻久久中文字幕| 日本三级久久网| 久久久久久精品无码人妻| 久久成人影院精品777| 久久免费看黄a级毛片| 狠狠色婷婷久久一区二区三区| 久久久精品波多野结衣| 国内精品久久久久影院优| 久久99精品久久久久久9蜜桃| 久久久久亚洲AV无码观看| 欧美综合天天夜夜久久| 亚洲精品视频久久久| 久久久久亚洲精品中文字幕| 久久久久亚洲精品天堂| 国产精品免费看久久久| 18禁黄久久久AAA片| 久久免费精品视频| 99久久国产综合精品麻豆| 久久久女人与动物群交毛片 | 久久久精品国产sm调教网站| 青春久久| 中文字幕无码久久精品青草| 91精品国产综合久久久久久| 久久Av无码精品人妻系列| 国产精品久久久久久久app| 国产福利电影一区二区三区久久久久成人精品综合 | 99久久精品国产毛片| 99久久人妻无码精品系列 | 久久国产精品-国产精品| 久久精品中文无码资源站| 伊人久久大香线焦AV综合影院| 东方aⅴ免费观看久久av | 99久久精品这里只有精品 | 国产精品中文久久久久久久| 亚洲精品视频久久久| 亚洲午夜无码AV毛片久久|