On the Complexity of Multiple Sequence Alignment | Zendy

Lusheng Wang | Zendy; Tao Jiang | Zendy

AI Assistant Blog Pricing

Home ZAIA Blog

Open Access

On the Complexity of Multiple Sequence Alignment

Author(s) -

Lusheng Wang,

Tao Jiang

Publication year - 1994

Publication title -

journal of computational biology

Language(s) - English

Resource type - Journals

SCImago Journal Rank - 0.585

H-Index - 95

eISSN - 1557-8666

pISSN - 1066-5277

DOI - 10.1089/cmb.1994.1.337

Subject(s) - multiple sequence alignment , alignment free sequence analysis , computational complexity theory , sequence (biology) , sequence alignment , tree (set theory) , computer science , algorithm , computational biology , mathematics , theoretical computer science , biology , combinatorics , genetics , gene , peptide sequence

We study the computational complexity of two popular problems in multiple sequence alignment: multiple alignment with SP-score and multiple tree alignment. It is shown that the first problem is NP-complete and the second is MAX SNP-hard. The complexity of tree alignment with a given phylogeny is also considered.

The content you want is available to Zendy users.

Already have an account? Click here to sign in.

Having issues? You can contact us here

Accelerating Research