Multiple sequence alignment with arbitrary gap costs: Computing an optimal 
solution using polyhedral combinatorics

Althaus, Ernst; Caprara, Alberto; Lenhof, Hans-Peter; Reinert, Knut; Lengauer, Thomas

Multiple sequence alignment with arbitrary gap costs: Computing an optimal solution using polyhedral combinatorics

Althaus, E., Caprara, A., Lenhof, H.-P., & Reinert, K. (2002). Multiple sequence alignment with arbitrary gap costs: Computing an optimal solution using polyhedral combinatorics. In Proceedings of the European Conference on Computational Biology (ECCB 2002) (pp. S4-S16). Oxford, UK: Oxford University Press.

Item is 公開

表示: 全項目非表示: 全項目

基本情報

表示: 非表示:

アイテムのパーマリンク: https://hdl.handle.net/11858/00-001M-0000-000F-3001-0 版のパーマリンク: https://hdl.handle.net/11858/00-001M-0000-000F-3003-C

資料種別: 会議論文

ファイル

表示: ファイル

作成者

表示:

非表示:

作成者:
Althaus, Ernst¹, 著者
Caprara, Alberto, 著者
Lenhof, Hans-Peter¹, 著者
Reinert, Knut¹, 著者
Lengauer, Thomas², 編集者

所属:
1Algorithms and Complexity, MPI for Informatics, Max Planck Society, ou_24019
2Computational Biology and Applied Algorithmics, MPI for Informatics, Max Planck Society, ou_40046

内容説明

表示:

非表示:

キーワード: -

要旨: Multiple sequence alignment is one of the dominant problems in computational molecular biology. Numerous scoring functions and methods have been proposed, most of which result in NP-hard problems. In this paper we propose for the first time a general formulation for multiple alignment with arbitrary gap-costs based on an integer linear program (ILP). In addition we describe a branch-and-cut algorithm to effectively solve the ILP to optimality. We evaluate the performances of our approach in terms of running time and quality of the alignments using the BAliBase database of reference alignments. The results show that our implementation ranks amongst the best programs developed so far.

資料詳細

表示:

非表示:

言語: eng - English

日付: 修正: 2003-08-28出版: 2002

出版の状態: 出版

ページ: -

出版情報: -

目次: -

査読: -

識別子（DOI, ISBNなど）: eDoc: 202065
その他: Local-ID: C1256428004B93B8-14DF56BBB5470A4DC1256C930054F370-Althaus2002b

学位: -

訴訟

表示:

Project information

表示:

出版物 1

表示:

非表示:

出版物名: Proceedings of the European Conference on Computational Biology (ECCB 2002)

種別: 会議論文集

著者・編者:

所属:

出版社, 出版地: Oxford, UK : Oxford University Press

ページ: - 巻号: - 通巻号: - 開始・終了ページ: S4 - S16 識別子（ISBN, ISSN, DOIなど）: -

出版物 2

表示:

非表示:

出版物名: Bioinformatics

種別: 連載記事

著者・編者:

所属:

出版社, 出版地: -

ページ: - 巻号: - 通巻号: - 開始・終了ページ: - 識別子（ISBN, ISSN, DOIなど）: -

アイテム詳細

基本情報

ファイル

関連URL

作成者

内容説明

資料詳細

関連イベント

訴訟

Project information

出版物 1

出版物 2