生物信息學中的若干組合問題.pdf

1、分 類 號 口 ‘刁、單 位 代 碼 學 號 沁 ” 叮 護功 縈尤 寒碩 士 學 位 論 文呂 力 ” 。 ” 口 ” 陽 鄺，吮 獷 ，論 文 題 目 生倒 議 倉寧 如 奸‘ 帥下 也姓 名 加 丙了 衣業(yè) 書 李 多為 利 奮 沙者 作 專指 導 教 師 姓 名專 業(yè) 技 術 職 務‘ 年 紛 月 、 藝 日山 東 大 學 碩 長學 位論 文生 物 信 息 學 中的 若 干 組 合 問 題劉 萬 強山 東 大 學數(shù) 學 與 系

2、統(tǒng) 科 學 學 院運 籌 學 與控 制 論東 濟 南中文 摘 要在 生 命科 學 中， 許 多 間 題 都 可 以 抽 象 為 計 算 機 科學 與 數(shù) 學 中關 于 序 列、 樹 和串的 組 合 間 題 本 文 主 要 研 究 兩 個 重 要 的 生 物 信 息學 問 題 尋 找 問 題 和折 亞 問題 這 兩 種 間 題 簡 言 之 都 是 在 許 多 生 物 學 序 列 中尋 找 共 同 部 分近 年 來， 生命 科 學 的 飛

3、速 發(fā) 展 帶 給 我 們 越 來 越 多 的 研 究 數(shù) 據(jù)， 如 何 在 這 些 浩如煙 海 的 數(shù)據(jù) 中挖 掘 有 用 的信 息 已 經 成 為 當 前 科學 家 們 需 要 面 對 的 首 要 間 題， 并由此 產 生 了研 究 生 命 的新 學 科 生 物 信 息 學， 它 以 生 物 學 實驗 室 研 究 的 數(shù) 據(jù) 為 材料， 利 用 網 絡 和 計 算 機 技 術， 來 實 現(xiàn) 對 生 命 本 質 的研 究、 探 索&#

4、183;本文 考慮 的 第 一 個 間 題 是 尋 找 間 題 在 生 物 學 中， 基 因 的 活 性 往 往 取決 于 一 些 稱為 的小 片段 的性 質， 尋 找 間 題 就 是 要 在 序 列 中找出這 些 小 的片段， 然 而， 往 往 并 不 以 本 來 面 貌 出 現(xiàn)， 合理 的 模 型 是 允 許 未 知的 片段 以 少 許錯 配、 擂 入 和 缺 失 的形 式 出現(xiàn) 在 所研 究 序列 中 我 們可 以 描 述 尋 找

5、間題 如 下 給 定 一 個 序 列 集， 以 及 一 個 未 知 片段， 這 個 片段 以 少 量 變 化 的 形式 諸 如 錯 配、 擂 入 和 缺 失 在 不 同 位 置 出 現(xiàn) 每個 序 列 中 序 列 中對 應 的 片段 即叫做， 我 們能 否 找 出這 些 呢 在 序 列 中尋 找 是 計 算 生物 學 中的 一 個 墓 本 間 題， 在 基 因 調 節(jié) 中有 十 分 重 要 的 應 用， 基 因 序列 數(shù) 量 的 巨 大讓

6、 問題 計 算起 來 相 當 困 難， 而 且 其 中的 許 多 間 題 都是一 的 近 十 年 來，人 們 為 此 設 計 了 許 多 啟 發(fā) 式 算 法， 但 問 題 還 遠 遠 沒 有解 決本 文 主 要 考 慮 變 異 的 兩 個 形 式 嵌 入 和 缺 失 即 允 許 未 知 片段 以 少 許嵌入 或 缺 失 的形 式 出 現(xiàn) 在 所 研 究 序 列 中 我 們刻 畫 間 題 如 下問題 嵌 人 問 題 給 定 藝 域 中的