MySQL query optimisation advice for search query

We are currently in the process of trying to re-write a very large and nasty dynamic search query. The search term for this query was 'red christmas napkins' and these 3 keywords have been added to using other knows synonyms to produce the full list searched against below (the query below is the end result that was ran on MySQL).

As I'm sure you will all notice very quickly there is far too much going on here but I wanted to get advice on how you would best re-write this for sheer query speed? The releveance scores against each individual term being search aren't completely random, they are dynamically calculated for each query based on a large number of factors incase anyone was wondering.

I have also inclded the MySQL responce when running EXPLAIN on the live DB server using the same query as below.

Thanks in advance for any help/insite you can provide.

SELECT p.pid, ((
    (MATCH (p.title)
        AGAINST ('red christmas napkin red xmas napkin red christmas napkins red 
            xmas napkins red christmas serviette red xmas serviette red christmas 
            serviettes red xmas serviettes' 
            IN BOOLEAN MODE)) * 10) + (
    (MATCH (p.code)
        AGAINST ('red christmas napkin red xmas napkin red christmas napkins red 
            xmas napkins red christmas serviette red xmas serviette red christmas 
            serviettes red xmas serviettes' 
            IN BOOLEAN MODE)) * 0.3) + (
    (MATCH (p.description)
        AGAINST ('red christmas napkin red xmas napkin red christmas napkins red 
            xmas napkins red christmas serviette red xmas serviette red christmas 
            serviettes red xmas serviettes' 
        IN BOOLEAN MODE)) * 0.2) + (
    (MATCH (p.search_keywords)
        AGAINST ('red christmas napkin red xmas napkin red christmas napkins red 
            xmas napkins red christmas serviette red xmas serviette red christmas 
            serviettes red xmas serviettes' 
        IN BOOLEAN MODE)) * 5) + 
    (IFNULL(
        (
            SELECT 10 
            FROM prod 
            WHERE live = 1 AND deleted = 0 AND title LIKE '%red christmas napkin 
                red xmas napkin red christmas napkins red xmas napkins red christmas 
                serviette red xmas serviette red christmas serviettes red xmas serviettes%' 
                AND pid = p.pid 
            LIMIT 1
    ), 0) * 10) + 
    (IFNULL(
        (
            SELECT 10 
            FROM prod 
            WHERE live = 1 AND deleted = 0 AND title LIKE '%red%' AND pid = p.pid 
            LIMIT 1
    ), 0) * 10.857142857143) + 
    (IFNULL(
        (
            SELECT 10 
            FROM prod 
            WHERE live = 1 AND deleted = 0 AND title LIKE '%christmas%' AND pid = p.pid 
            LIMIT 1
    ), 0) * 10.714285714286) + 
    (IFNULL(
        (
            SELECT 10 
            FROM prod 
            WHERE live = 1 AND deleted = 0 AND title LIKE '%napkin%' AND pid = p.pid 
            LIMIT 1
    ), 0) * 10.571428571429) + 
    (IFNULL(
        (
            SELECT 10 
            FROM prod 
            WHERE live = 1 AND deleted = 0 AND title LIKE '%xmas%' AND pid = p.pid 
            LIMIT 1
    ), 0) * 10.428571428571) + 
    (IFNULL(
        (
            SELECT 10 
            FROM prod 
            WHERE live = 1 AND deleted = 0 AND title LIKE '%napkins%' AND pid = p.pid 
            LIMIT 1
    ), 0) * 10.285714285714) + 
    (IFNULL(
        (
            SELECT 10 
            FROM prod 
            WHERE live = 1 AND deleted = 0 AND title LIKE '%serviette%' AND pid = p.pid 
            LIMIT 1
    ), 0) * 10.142857142857) + 
    (IFNULL(
        (
            SELECT 10 
            FROM prod 
            WHERE live = 1 AND deleted = 0 AND title LIKE '%serviettes%' AND pid = p.pid 
            LIMIT 1
    ), 0) * 10)
) AS 'relevance'
FROM prod p
LEFT JOIN prod_link_cat ON prod_link_cat.pid = p.pid
LEFT JOIN cat ON prod_link_cat.link_cid = cat.cid
    AND p.pid = prod_link_cat.pid
LEFT JOIN brand ON brand.bid = p.bid
    AND brand.live = 1
    AND brand.deleted = 0
WHERE p.live = 1
    AND p.deleted = 0
GROUP BY p.pid
HAVING relevance > 0
ORDER BY prod_link_cat.position ASC
LIMIT 0, 12

(explain)

id  select_type         table         type          possible_keys               key             key_len ref        rows  Extra 
1   PRIMARY             p             index_merge   live,deleted                deleted,live    1,1     NULL       1171 Using intersect(deleted,live); Using where; Using temporary; Using filesort
1   PRIMARY             prod_link_cat ref           pid                         pid             4       sryg.p.pid  4   
1   PRIMARY             cat           eq_ref        PRIMARY                     PRIMARY         4       sryg.prod_link_cat.link_cid 1   Using index
1   PRIMARY             brand         eq_ref        PRIMARY,live,live_2,live_3  PRIMARY         4       sryg.p.bid  1   
9   DEPENDENT SUBQUERY  prod          eq_ref        PRIMARY,live,deleted        PRIMARY         4       func        1   Using where
8   DEPENDENT SUBQUERY  prod          eq_ref        PRIMARY,live,deleted        PRIMARY         4       func        1   Using where
7   DEPENDENT SUBQUERY  prod          eq_ref        PRIMARY,live,deleted        PRIMARY         4       func        1   Using where
6   DEPENDENT SUBQUERY  prod          eq_ref        PRIMARY,live,deleted        PRIMARY         4       func        1   Using where
5   DEPENDENT SUBQUERY  prod          eq_ref        PRIMARY,live,deleted        PRIMARY         4       func        1   Using where
4   DEPENDENT SUBQUERY  prod          eq_ref        PRIMARY,live,deleted        PRIMARY         4       func        1   Using where
3   DEPENDENT SUBQUERY  prod          eq_ref        PRIMARY,live,deleted        PRIMARY         4       func        1   Using where
2   DEPENDENT SUBQUERY  prod          eq_ref        PRIMARY,live,deleted        PRIMARY         4       func        1   Using where