Parametric multiple sequence alignment and phylogeny construction

被引：9

作者：

Fernández-Baca, David ^{[1
]}

Seppäläinen, Timo ^{[2
]}

Slutzki, Giora ^{[1
]}

机构：

[1] Department of Computer Science, Iowa State University, Ames

[2] Department of Mathematics, University of Wisconsin-Madison, Madison

来源：

Journal of Discrete Algorithms | 2004年 / 2卷 / 2 SPEC. ISS.期

关键词：

Alignment; Computational biology; Evolutionary tree; Multiple alignment; Phylogenetic tree; Sensitivity analysis;

D O I：

10.1016/S1570-8667(03)00078-9

中图分类号：

学科分类号：

摘要：

Bounds are given on the size of the parameter-space decomposition induced by multiple sequence alignment problems where phylogenetic information may be given or inferred. It is shown that many of the usual formulations of these problems fall within the same integer parametric framework, implying that the number of distinct optima obtained as the parameters are varied across their ranges is polynomially bounded in the length and number of sequences. © 2003 Elsevier B.V. All rights reserved.

引用

页码：271 / 287

页数：16

共 38 条

[1]

Agarwal P.K., Sharir M., Davenport-Schinzel Sequences and Their Geometric Applications, (1995)

[2]

Altschul S.F., Gap costs for multiple sequence alignment, J. Theor. Biol., 138, pp. 297-309, (1989)

[3]

Altschul S.F., Leaf pairs and tree dissections, SIAM J. Discrete Math., 2, 3, pp. 293-299, (1989)

[4]

Altschul S.F., Carrol R.J., Lipman D.J., Weights for data related by a tree, J. Mol. Biol., 207, pp. 647-653, (1989)

[5]

Altschul S.F., Lipman D.J., Trees, stars, and multiple biological sequence alignment, SIAM J. Appl. Math., 49, 1, pp. 197-209, (1989)

[6]

Dayhoff M.O., Schwarte R.M., Orcutt B.C., A model of evolutionary change in proteins, Atlas of Protein Sequence and Structure, 5, pp. 345-352, (1978)

[7]

Dobkin D., Edelsbrunner H., Yap C.K., Probing convex polytopes, Proceedings of the 18th Annual ACM Symposium on Theory of Computing, pp. 424-432, (1986)

[8]

Dobkin D., Edelsbrunner H., Yap C.K., Probing convex polytopes, Autonomous Robot Vehicles, pp. 328-341, (1990)

[9]

Edelsbrunner H., Algorithms in Combinatorial Geometry, (1987)

[10]

Eisner M.J., Severance D.G., Mathematical techniques for efficient record segmentation in large shared databases, J. Assoc. Comput. Mach., 23, pp. 619-635, (1976)

← 1 2 3 4 →