A characterization of nested canalyzing functions with maximum average sensitivity

Nested canalyzing functions (NCFs) are a class of Boolean functions which are used to model certain biological phenomena. We derive a complete characterization of NCFs with the largest average sensitivity, expressed in terms of a simple structural property of the NCF. This characterization provides...

Full description

Saved in:
Bibliographic Details
Published in:Discrete Applied Mathematics 2018-12, Vol.251, p.5-14
Main Authors: Stearns, Richard E., Rosenkrantz, Daniel J., Ravi, S.S., Marathe, Madhav V.
Format: Article
Language:English
Subjects:
Boolean algebra
Boolean functions
Characterization
Combinatorics
Counting
Maximum average sensitivity
Maximum likelihood method
Nested canalyzing functions
Sensitivity
Upper bounds
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
cited_by cdi_FETCH-LOGICAL-c368t-135f1c4c9ce286cde2c9bb66c2d64f98ade2e2025e8d33bc3319db64d98dfa283
cites cdi_FETCH-LOGICAL-c368t-135f1c4c9ce286cde2c9bb66c2d64f98ade2e2025e8d33bc3319db64d98dfa283
container_end_page 14
container_issue
container_start_page 5
container_title Discrete Applied Mathematics
container_volume 251
creator Stearns, Richard E.
Rosenkrantz, Daniel J.
Ravi, S.S.
Marathe, Madhav V.
description Nested canalyzing functions (NCFs) are a class of Boolean functions which are used to model certain biological phenomena. We derive a complete characterization of NCFs with the largest average sensitivity, expressed in terms of a simple structural property of the NCF. This characterization provides an alternate, but elementary, proof of the tight upper bound on the average sensitivity of any NCF established by Klotz et al. (2013). We also utilize the characterization to derive a closed form expression for the number of NCFs that have the largest average sensitivity.
doi_str_mv 10.1016/j.dam.2018.05.014
format article
fullrecord <record><control><sourceid>proquest_cross</sourceid><recordid>TN_cdi_proquest_journals_2166094711</recordid><sourceformat>XML</sourceformat><sourcesystem>PC</sourcesystem><els_id>S0166218X18302725</els_id><sourcerecordid>2166094711</sourcerecordid><originalsourceid>FETCH-LOGICAL-c368t-135f1c4c9ce286cde2c9bb66c2d64f98ade2e2025e8d33bc3319db64d98dfa283</originalsourceid><addsrcrecordid>eNp9kN9LwzAQx4MoOKd_gG8Bn1tzaZum-DTEXzAQRMG3kCbXLWVtZ9JNt7_ejPns03F33-_xvQ8h18BSYCBu29TqLuUMZMqKlEF-QiYgS56IsoRTMokakXCQn-fkIoSWMQaxm5C3GTVL7bUZ0bu9Ht3Q06GhPYYRLTW616vd3vUL2mx6c9gG-u3GJe30j-s2HdVb9HqBNGAf3Oi2btxdkrNGrwJe_dUp-Xh8eL9_TuavTy_3s3liMiHHBLKiAZObyiCXwljkpqprIQy3Im8qqeMEOeMFSptltckyqGwtcltJ22gusym5Od5d--FrEwOrdtj4GDgoHr9lVV4CRBUcVcYPIXhs1Nq7TvudAqYO6FSrIjp1QKdYoSK66Lk7ejDG3zr0KhiHvUHrPJpR2cH94_4FGh94dw</addsrcrecordid><sourcetype>Aggregation Database</sourcetype><iscdi>true</iscdi><recordtype>article</recordtype><pqid>2166094711</pqid></control><display><type>article</type><title>A characterization of nested canalyzing functions with maximum average sensitivity</title><source>ScienceDirect Journals</source><creator>Stearns, Richard E. ; Rosenkrantz, Daniel J. ; Ravi, S.S. ; Marathe, Madhav V.</creator><creatorcontrib>Stearns, Richard E. ; Rosenkrantz, Daniel J. ; Ravi, S.S. ; Marathe, Madhav V.</creatorcontrib><description>Nested canalyzing functions (NCFs) are a class of Boolean functions which are used to model certain biological phenomena. We derive a complete characterization of NCFs with the largest average sensitivity, expressed in terms of a simple structural property of the NCF. This characterization provides an alternate, but elementary, proof of the tight upper bound on the average sensitivity of any NCF established by Klotz et al. (2013). We also utilize the characterization to derive a closed form expression for the number of NCFs that have the largest average sensitivity.</description><identifier>ISSN: 0166-218X</identifier><identifier>EISSN: 1872-6771</identifier><identifier>DOI: 10.1016/j.dam.2018.05.014</identifier><language>eng</language><publisher>Amsterdam: Elsevier B.V</publisher><subject>Boolean algebra ; Boolean functions ; Characterization ; Combinatorics ; Counting ; Maximum average sensitivity ; Maximum likelihood method ; Nested canalyzing functions ; Sensitivity ; Upper bounds</subject><ispartof>Discrete Applied Mathematics, 2018-12, Vol.251, p.5-14</ispartof><rights>2018 Elsevier B.V.</rights><rights>Copyright Elsevier BV Dec 31, 2018</rights><lds50>peer_reviewed</lds50><oa>free_for_read</oa><woscitedreferencessubscribed>false</woscitedreferencessubscribed><citedby>FETCH-LOGICAL-c368t-135f1c4c9ce286cde2c9bb66c2d64f98ade2e2025e8d33bc3319db64d98dfa283</citedby><cites>FETCH-LOGICAL-c368t-135f1c4c9ce286cde2c9bb66c2d64f98ade2e2025e8d33bc3319db64d98dfa283</cites><orcidid>0000-0002-0893-4364</orcidid></display><links><openurl>$$Topenurl_article</openurl><openurlfulltext>$$Topenurlfull_article</openurlfulltext><thumbnail>$$Tsyndetics_thumb_exl</thumbnail><link.rule.ids>314,780,784,27924,27925</link.rule.ids></links><search><creatorcontrib>Stearns, Richard E.</creatorcontrib><creatorcontrib>Rosenkrantz, Daniel J.</creatorcontrib><creatorcontrib>Ravi, S.S.</creatorcontrib><creatorcontrib>Marathe, Madhav V.</creatorcontrib><title>A characterization of nested canalyzing functions with maximum average sensitivity</title><title>Discrete Applied Mathematics</title><description>Nested canalyzing functions (NCFs) are a class of Boolean functions which are used to model certain biological phenomena. We derive a complete characterization of NCFs with the largest average sensitivity, expressed in terms of a simple structural property of the NCF. This characterization provides an alternate, but elementary, proof of the tight upper bound on the average sensitivity of any NCF established by Klotz et al. (2013). We also utilize the characterization to derive a closed form expression for the number of NCFs that have the largest average sensitivity.</description><subject>Boolean algebra</subject><subject>Boolean functions</subject><subject>Characterization</subject><subject>Combinatorics</subject><subject>Counting</subject><subject>Maximum average sensitivity</subject><subject>Maximum likelihood method</subject><subject>Nested canalyzing functions</subject><subject>Sensitivity</subject><subject>Upper bounds</subject><issn>0166-218X</issn><issn>1872-6771</issn><fulltext>true</fulltext><rsrctype>article</rsrctype><creationdate>2018</creationdate><recordtype>article</recordtype><recordid>eNp9kN9LwzAQx4MoOKd_gG8Bn1tzaZum-DTEXzAQRMG3kCbXLWVtZ9JNt7_ejPns03F33-_xvQ8h18BSYCBu29TqLuUMZMqKlEF-QiYgS56IsoRTMokakXCQn-fkIoSWMQaxm5C3GTVL7bUZ0bu9Ht3Q06GhPYYRLTW616vd3vUL2mx6c9gG-u3GJe30j-s2HdVb9HqBNGAf3Oi2btxdkrNGrwJe_dUp-Xh8eL9_TuavTy_3s3liMiHHBLKiAZObyiCXwljkpqprIQy3Im8qqeMEOeMFSptltckyqGwtcltJ22gusym5Od5d--FrEwOrdtj4GDgoHr9lVV4CRBUcVcYPIXhs1Nq7TvudAqYO6FSrIjp1QKdYoSK66Lk7ejDG3zr0KhiHvUHrPJpR2cH94_4FGh94dw</recordid><startdate>20181231</startdate><enddate>20181231</enddate><creator>Stearns, Richard E.</creator><creator>Rosenkrantz, Daniel J.</creator><creator>Ravi, S.S.</creator><creator>Marathe, Madhav V.</creator><general>Elsevier B.V</general><general>Elsevier BV</general><scope>AAYXX</scope><scope>CITATION</scope><scope>7SC</scope><scope>8FD</scope><scope>JQ2</scope><scope>L7M</scope><scope>L~C</scope><scope>L~D</scope><orcidid>https://orcid.org/0000-0002-0893-4364</orcidid></search><sort><creationdate>20181231</creationdate><title>A characterization of nested canalyzing functions with maximum average sensitivity</title><author>Stearns, Richard E. ; Rosenkrantz, Daniel J. ; Ravi, S.S. ; Marathe, Madhav V.</author></sort><facets><frbrtype>5</frbrtype><frbrgroupid>cdi_FETCH-LOGICAL-c368t-135f1c4c9ce286cde2c9bb66c2d64f98ade2e2025e8d33bc3319db64d98dfa283</frbrgroupid><rsrctype>articles</rsrctype><prefilter>articles</prefilter><language>eng</language><creationdate>2018</creationdate><topic>Boolean algebra</topic><topic>Boolean functions</topic><topic>Characterization</topic><topic>Combinatorics</topic><topic>Counting</topic><topic>Maximum average sensitivity</topic><topic>Maximum likelihood method</topic><topic>Nested canalyzing functions</topic><topic>Sensitivity</topic><topic>Upper bounds</topic><toplevel>peer_reviewed</toplevel><toplevel>online_resources</toplevel><creatorcontrib>Stearns, Richard E.</creatorcontrib><creatorcontrib>Rosenkrantz, Daniel J.</creatorcontrib><creatorcontrib>Ravi, S.S.</creatorcontrib><creatorcontrib>Marathe, Madhav V.</creatorcontrib><collection>CrossRef</collection><collection>Computer and Information Systems Abstracts</collection><collection>Technology Research Database</collection><collection>ProQuest Computer Science Collection</collection><collection>Advanced Technologies Database with Aerospace</collection><collection>Computer and Information Systems Abstracts – Academic</collection><collection>Computer and Information Systems Abstracts Professional</collection><jtitle>Discrete Applied Mathematics</jtitle></facets><delivery><delcategory>Remote Search Resource</delcategory><fulltext>fulltext</fulltext></delivery><addata><au>Stearns, Richard E.</au><au>Rosenkrantz, Daniel J.</au><au>Ravi, S.S.</au><au>Marathe, Madhav V.</au><format>journal</format><genre>article</genre><ristype>JOUR</ristype><atitle>A characterization of nested canalyzing functions with maximum average sensitivity</atitle><jtitle>Discrete Applied Mathematics</jtitle><date>2018-12-31</date><risdate>2018</risdate><volume>251</volume><spage>5</spage><epage>14</epage><pages>5-14</pages><issn>0166-218X</issn><eissn>1872-6771</eissn><abstract>Nested canalyzing functions (NCFs) are a class of Boolean functions which are used to model certain biological phenomena. We derive a complete characterization of NCFs with the largest average sensitivity, expressed in terms of a simple structural property of the NCF. This characterization provides an alternate, but elementary, proof of the tight upper bound on the average sensitivity of any NCF established by Klotz et al. (2013). We also utilize the characterization to derive a closed form expression for the number of NCFs that have the largest average sensitivity.</abstract><cop>Amsterdam</cop><pub>Elsevier B.V</pub><doi>10.1016/j.dam.2018.05.014</doi><tpages>10</tpages><orcidid>https://orcid.org/0000-0002-0893-4364</orcidid><oa>free_for_read</oa></addata></record>
fulltext fulltext
identifier ISSN: 0166-218X
ispartof Discrete Applied Mathematics, 2018-12, Vol.251, p.5-14
issn 0166-218X
1872-6771
language eng
recordid cdi_proquest_journals_2166094711
source ScienceDirect Journals
subjects Boolean algebra
Boolean functions
Characterization
Combinatorics
Counting
Maximum average sensitivity
Maximum likelihood method
Nested canalyzing functions
Sensitivity
Upper bounds
title A characterization of nested canalyzing functions with maximum average sensitivity
url http://sfxeu10.hosted.exlibrisgroup.com/loughborough?ctx_ver=Z39.88-2004&ctx_enc=info:ofi/enc:UTF-8&ctx_tim=2025-01-05T06%3A48%3A35IST&url_ver=Z39.88-2004&url_ctx_fmt=infofi/fmt:kev:mtx:ctx&rfr_id=info:sid/primo.exlibrisgroup.com:primo3-Article-proquest_cross&rft_val_fmt=info:ofi/fmt:kev:mtx:journal&rft.genre=article&rft.atitle=A%20characterization%20of%20nested%20canalyzing%20functions%20with%20maximum%20average%20sensitivity&rft.jtitle=Discrete%20Applied%20Mathematics&rft.au=Stearns,%20Richard%20E.&rft.date=2018-12-31&rft.volume=251&rft.spage=5&rft.epage=14&rft.pages=5-14&rft.issn=0166-218X&rft.eissn=1872-6771&rft_id=info:doi/10.1016/j.dam.2018.05.014&rft_dat=%3Cproquest_cross%3E2166094711%3C/proquest_cross%3E%3Cgrp_id%3Ecdi_FETCH-LOGICAL-c368t-135f1c4c9ce286cde2c9bb66c2d64f98ade2e2025e8d33bc3319db64d98dfa283%3C/grp_id%3E%3Coa%3E%3C/oa%3E%3Curl%3E%3C/url%3E&rft_id=info:oai/&rft_pqid=2166094711&rft_id=info:pmid/&rfr_iscdi=true