生物信息學(xué)中的若干組合問(wèn)題.pdf

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

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

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

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

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

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