11 September 2012 Last updated at 07:17 GMT
Profile: Al-Qaeda in the Arabian Peninsula
Led by a former aide to Osama Bin Laden, the group has vowed to attack oil facilities, foreigners and security forces as it seeks to topple the Saudi monarchy and Yemeni government, and establish an Islamic caliphate.
It has claimed responsibility for a number of attacks in the two countries over the past 12 months, and has been blamed by President Barack Obama for attempting to blow up a US passenger jet as it flew into Detroit on Christmas Day.
A Nigerian man charged in relation to the incident, Umar Farouk Abdulmutallab, has allegedly told investigators that AQAP operatives trained him in Yemen, equipped him with a powerful explosive device and told him what to do.
He also warned there were others like him who would strike soon.
Beheading Al-Qaeda in the Arabian Peninsula first came to prominence in Saudi Arabia in May 2003, when it claimed responsibility for simultaneous suicide bombing attacks on three Western housing compounds in Riyadh, which left 29 dead.
Despite a subsequent crackdown on Islamist militants and radicals by the Saudi security forces, the group was able to mount an attack on the Muhayyah residential compound in the capital that November, killing 17 people.
In 2004, it suffered a major blow when its leader, Khaled Ali Hajj - a Yemeni and former bodyguard of Bin Laden - was ambushed and killed by Saudi troops.
However, the group soon recovered under the guidance of a veteran Saudi militant, Abdul Aziz al-Muqrin, and launched a series of spectacular attacks.
On 1 May 2004, militants shot dead five Western workers at a petrochemical complex in the north-western Red Sea city of Yanbu. On 29 May, more than 20 foreign and Saudi nationals were killed in attacks on three sites in the city of al-Khobar, increasing fears of political instability and pushing up global oil prices.
The following month, members of AQAP abducted and beheaded a 49-year old American aerospace worker named Paul Johnson.
Al-Qaeda in the Arabian Peninsula
- Formed in January 2009 by a merger between al-Qaeda in Saudi Arabia and Yemen
- Based in eastern Yemen
- Led by Nasser al-Wuhayshi, a Yemeni former aide to Osama Bin Laden. Deputy leader Saudi ex-Guantanamo inmate Said al-Shihri reported killed in September 2012
- Aims to topple Saudi monarchy and Yemeni government, and establish an Islamic caliphate
- Came to prominence with Riyadh bombings in 2003, and 2008 attack on US embassy in Sanaa
- Says it was behind an attempt to blow up US passenger jet in December 2009
The Saudi security services gradually gained the upper hand, and succeed in preventing any major attacks the following year, when Awfi was himself killed during a police raid in the holy city of Medina.
In spite of the large numbers of Saudis who then travelled to militant training camps and gained experience fighting in places such as Iraq, the group found it increasingly difficult to organise operational cells inside the kingdom. Its last attempt a significant attack was at the Abqaiq oil facility in February 2006.
Prison escape Meanwhile in Yemen - the ancestral home of Bin Laden - Sunni militants took advantage of the weak central government, whose authority does not extend far outside the capital Sanaa, and established strongholds in its largely autonomous tribal regions.
Although al-Qaeda cells were held responsible for several attacks inside Yemen since the suicide boat attack on the USS Cole near the port of Aden in 2000 that killed 17 US sailors, it was not until the second half of the decade that a fully-functioning affiliated group was formed.
According to Gregory Johnsen of Princeton University, between 2002 and 2003 the Yemeni government co-operated closely with the US to fight al-Qaeda. By the end of that period - which included one leader being killed in a controversial strike by a CIA drone aircraft - al-Qaeda appeared to be substantially weakened and so both countries shifted focus.
The policy appeared to have worked until February 2006, Mr Johnsen says, when 23 suspected al-Qaeda members managed to escape from a prison in Sanaa, including Jamal al-Badawi, the alleged mastermind of the USS Cole bombing.
Most were eventually either recaptured or killed, but two of the lesser-known escapees eluded the authorities, including Nasser Abdul Karim al-Wuhayshi, a former personal assistant to Bin Laden in Afghanistan, and Qasim al-Raymi.
A 33-year-old from the southern governorate of al-Baida, Wuhayshi spent time in religious institutions in Yemen before travelling to Afghanistan in the late 1990s. He fought at the battle of Tora Bora in December 2001, before escaping over the border into Iran, where he was eventually arrested. He was extradited to Yemen in 2003.
After escaping from prison, Wuhayshi and Raymi are said to have overseen the formation of al-Qaeda in Yemen, which took in both new recruits and experienced Arab fighters returning from Iraq and Afghanistan. Protected by tribes who were wary of government interference, the group established bases from which to launch fresh attacks.
The group claimed responsibility for two suicide bomb attacks that killed six Western tourists before being linked to the assault on the US embassy in Sanaa in September 2008, in which militants detonated bombs and fired rocket-propelled grenades. Ten Yemeni guards and four civilians were killed, along with six assailants.
Four months later, Wuhayshi announced in a video the merger of the al-Qaeda offshoots in Yemen and Saudi Arabia to form "al-Qaeda of Jihad Organisation in the Arabian Peninsula".
Analysts say the move was designed to bring Saudi al-Qaeda members who had fled their country and Yemeni militants together under one umbrella as a first step towards launching attacks throughout the region.
Next to Wuhayshi and Raymi, the group's military commander, in the same video sat the new deputy leader, Said Ali al-Shihri, a Saudi national who was released from the US military detention centre at Guantanamo Bay in November 2007.
Another former detainee, Mohammed Atiq al-Harbi, also known as Mohammed al-Awfi, appeared alongside them and was described as a field commander.
Embarrassingly for both Riyadh and Washington, both men had been released from Guantanamo into the custody of the Saudi government's "deradicalisation" programme for militants, which includes art therapy. They both left the facility within weeks.
The group's first operation outside Yemen was carried out in Saudi Arabia in August 2009 against the kingdom's security chief, Prince Mohammed bin Nayef, though he survived. The bomber, Ahmed al-Asiri, concealed a device containing the high-explosive pentaerythritol tetranitrate (PETN) inside his body.
His brother, Ibrahim, is believed to have made the bomb, as well as the device used in the failed attempt to destroy the Northwest Airlines Airbus A330 on Christmas Day.
After news of the latter incident emerged, AQAP released a statement saying it had sought to avenge recent raids by Yemeni forces aided by US intelligence, in which dozens of militants are reported to have died.
"We tell the American people that since you support the leaders who kill our women and children... we have come to slaughter you [and] will strike you with no previous [warning], our vengeance is near," the group said.
"We call on all Muslims... to throw out all unbelievers from the Arabian Peninsula by killing crusaders who work in embassies or elsewhere... [in] a total war on all crusaders in the Peninsula of Muhammad."
Government offensive Following the bombing attempt, Yemeni government forces launched a major offensive against AQAP, targeting the organisation's senior leaders and training camps in the governorates of Shabwa, Abyan and Marib.
They were supported heavily by the US, which sent advisers, provided intelligence, deployed unmanned drones and fired cruise missiles.
Though officials claimed six leaders were killed, the offensive was considered largely unsuccessful. Instead of decapitating AQAP and disrupting its operations, the group shifted its strategy and stepped up its attacks inside Yemen.
AQAP subsequently carried out a series of armed assaults and bombings on military, civilian and diplomatic targets, leaving dozens of security personnel and civilians dead, according to local reports.
In February 2010, Qasim al-Raymi issued a statement threatening the US.
"Today, you have attacked us in the middle of our household, so wait for what will befall you in the middle of yours," he said. "We will blow up the earth from beneath your feet".
Eight months later, the group was accused of sending bombs hidden in two packages addressed to synagogues in the US city of Chicago, which were found on planes in Dubai and the UK.
Both were shipped from Yemen and used PETN, the explosive that was also used in the two earlier attacks on Prince Mohammed bin Nayef and the Northwest Airlines passenger jet. One of the detonators was also almost exactly the same as the one used by Mr Abdulmutallab. US officials said Ibrahim al-Asiri had made them.
Al-Qaeda in the Arabian Peninsula also began targeting the Zaidi Shia group, al-Shabab al-Muminin. Fighting between the group - led by Abdul Malik al-Houthi and also known as the Houthis - and the Yemeni military over the past seven years has left thousands of people dead in the north.
In November 2010, AQAP carried out two suicide car bomb attacks on Houthi religious processions in al-Jawf and Maarib governorates, killing a total of 25 people.
The continuing offensive against AQAP reportedly scored a success in September 2012, when the Yemeni government announced al-Shiri had been killed in the south of the country. Some accounts say Yemeni troops were involved, others that it was an air strike, possibly a US drone attack.
Reports on Al-Qaeda in the Arabian Peninsula's membership vary wildly - some experts say there are fewer than 50 fighters, while others believe there may be 200 to 300 - but most agree that if it is left unmolested it will soon become a major threat.